Hello there, in this article we will show how to find if a graph is a Bipartite Graph through detailed examples.
1. Introduction
In this article, we will define a bipartite graph, explore the properties of a bipartite graph, document an algorithm used to determine whether a graph is bipartite or not, and implement this algorithm in Java.
Finally, we will discuss the Time Complexity of various ways of implementing this algorithm.
2. Bipartite graph examples
A real-life application of a bipartite graph may be the use of vertices or nodes to represent entities in biological systems such as proteins, genes, and other molecules and the relationships between them which are indicated by edges. Another may be the utilization in order to establish relationships between attributes of individuals and their resultant compatibilities represented by edges in a dating site app.
3. Definitions
| Term | Description |
| Vertex | Used to represent an entity or location, for example, cities, buildings can be represented by a vertex |
| Edge | Used to represent a relationship between vertices |
| Graph | Contains vertices and edges |
| Bipartite Graph | A graph in which vertices can be placed into either one of two sets, with the properties enumerated in the following section (Properties of Bipartite Graphs). |
| Self Edge | An edge that links a vertex to itself |
| Undirected Graph | A graph in which a vertex A that links to another vertex B, will have vertex B reciprocally link to vertex A |
| Adjacency List | A list that represents other vertices linked to a particular vertex. |
| Adjacency Matrix | A matrix (rows of columns, R x C) that represent edges found between vertices. |
4. Properties of Bipartite Graphs
- Vertices can be separated into 2 separate sets.
- A vertex can belong to only one set and not the other.
- Vertices of one set can only have edges with vertices of the other set.
- Vertices of one set will not have edges with vertices within the set they belong to.
- Vertices will not have edges with themselves.
5. Algorithm to Determine if a Graph is Bipartite
Vertices can be numbered from 0 to N-1, where N is the number
of vertices being considered.
Create an array of size N initialized to UNASSIGNED. This array will contain
an indication of whether a vertex is in set 1 or set 2 when the
code has completed.
choose a vertex from 0 to N-1.
update the corresponding array element with set indicator, set_1 or set_2.
place vertex in a queue (list).
while the list has a vertex
remove the first vertex from the queue
for all of the vertices which have edges with this vertex,
if they have been assigned already and if it has the same set indicator
this is not a bipartite graph
otherwise assign the opposite set indicator
put the vertex just assigned a set indicator to the queue.
if there are no more vertices determine if there are any more unassigned vertices
if there are unassigned vertices, assign a set to it and add that to the queue
if no more, we are done.6. Implementation
This implementation will illustrate the determination of whether an undirected graph with no self edges is a bipartite graph by separating each vertex into one of two sets. Every vertex will belong to either set 1 or set 2 but not both. The implementation will use an adjacency matrix to represent the edges of the graph. One indicates an edge and a zero indicates no edge exists.
6.1 Sample Code
import java.util.ArrayList;
public class GraphIsBipartite {
final static int UNASSIGNED = 0;
final static int SET_1 = 1;
final static int SET_2 = 2;
public static boolean isUndirectedGraph(int [][] graphAdjacencyMap) {
boolean rv = true;
for (int i = 0; i < graphAdjacencyMap.length; i++) {
for (int j = 0; j < graphAdjacencyMap[i].length; j++) {
if (graphAdjacencyMap[i][j] != graphAdjacencyMap[j][i]) {
rv = false;
System.out.printf("failed undirected Test: map[%d][%d]: %d map[%d][%d]: %d\n", i, j, graphAdjacencyMap[i][j], j, i, graphAdjacencyMap[j][i]);
break;
}
}
}
return rv;
}
public static boolean hasSelfEdge(int [][] graphAdjacencyMap) {
boolean rv = false;
for (int i = 0; i < graphAdjacencyMap.length; i++) {
if (graphAdjacencyMap[i][i] == 1) {
rv = true;
System.out.printf("self edge map[%d][%d]: %d\n", i, i, graphAdjacencyMap[i][i]);
break;
}
}
return rv;
}
public static int nextUnassigned(int [] assigned) {
int unassigned = -1;
for (int i = 0; i < assigned.length; i++) {
if (assigned[i] == UNASSIGNED) {
unassigned = i;
break;
}
}
return unassigned;
}
public static boolean isBipartite(int [][] graphAdjacencyMap) {
boolean rv = true;
int index = 0;
ArrayList<Integer>al = new ArrayList<Integer>();
int [] setAssignment = new int[graphAdjacencyMap.length];
for(int i = 0; i < setAssignment.length; i++)
setAssignment[i] = UNASSIGNED;
setAssignment[index] = SET_1;
al.add(index);
while(al.size() > 0 && rv) {
int u = al.get(0);
al.remove(0);
for(int v = 0; v < setAssignment.length; v++) {
if(graphAdjacencyMap[u][v] == 1) {
if (setAssignment[v] == UNASSIGNED) {
if(setAssignment[u] == SET_1)
setAssignment[v] = SET_2;
else if(setAssignment[u] == SET_2)
setAssignment[v] = SET_1;
al.add(v);
} else if(setAssignment[v] == setAssignment[u]) {
rv = false;
break;
}
}
}
if (al.size() == 0) {
if (nextUnassigned(setAssignment) >= 0) {
index = nextUnassigned(setAssignment);
al.add(index);
setAssignment[index] = SET_1;
}
}
}
if (rv) {
String set1 = "";
String set2 = "";
for (int i = 0; i < setAssignment.length; i++) {
if (setAssignment[i] == SET_1) {
if (set1.length() > 0)
set1 += ", ";
set1 += i;
} else if (setAssignment[i] == SET_2) {
if (set2.length() > 0)
set2 += ", ";
set2 += i;
}
}
System.out.println(String.format(" SET_1 [ %s ]", set1));
System.out.println(String.format(" SET_2 [ %s ]", set2));
}
return rv;
}
public static boolean isValidMap(int [][] graphAdjacencyMap) {
boolean rv = true;
for (int i = 0; i < graphAdjacencyMap.length; i++) {
if (graphAdjacencyMap[i].length != graphAdjacencyMap.length) {
rv = false;
break;
}
}
return rv;
}
public static void printMap(int [][] map) {
String output = "[\n";
for (int i = 0; i < map.length; i++) {
output += " [ ";
for (int j = 0; j < map[i].length; j++) {
if (j != 0)
output += ", ";
output += String.format("%2d", map[i][j]);
}
output += " ],\n";
}
output += "]\n";
System.out.println(output);
}
public static String repeat(String repeatStr, int times) {
String str = "";
for (int i = 0; i < times; i++) str += repeatStr;
return str;
}
public static void main(String [] args) {
int [][][] graphAdjacencyMaps = {
// is bipartite
{
{0, 0, 1, 0, 1},
{0, 0, 0, 1, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{1, 0, 0, 0, 0},
},
{
{0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 0}
},
// is not bipartite
{
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
},
};
for (int [][] graphAdjacencyMap: graphAdjacencyMaps) {
System.out.println(repeat("*", 40));
printMap(graphAdjacencyMap);
if (isValidMap(graphAdjacencyMap)) {
if (!hasSelfEdge(graphAdjacencyMap)) {
if (isUndirectedGraph(graphAdjacencyMap)) {
if (isBipartite(graphAdjacencyMap)) {
System.out.println("Is bipartite");
} else
System.out.println("Is not bipartite");
} else {
System.out.println("This graph is undirected. Cannot be processed");
}
} else {
System.out.println("This graph has self edge. Cannot be processed");
}
} else {
System.out.println("This graph is not a square matrix. Cannot be processed");
}
System.out.println(repeat("*", 40));
}
}
}
6.2 Sample Code Output
****************************************
[
[ 0, 0, 1, 0, 1 ],
[ 0, 0, 0, 1, 0 ],
[ 1, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0 ],
[ 1, 0, 0, 0, 0 ],
]
SET_1 [ 0, 1 ]
SET_2 [ 2, 3, 4 ]
Is bipartite
****************************************
****************************************
[
[ 0, 1, 0, 0, 0, 1 ],
[ 1, 0, 1, 0, 0, 0 ],
[ 0, 1, 0, 1, 0, 0 ],
[ 0, 0, 1, 0, 1, 0 ],
[ 0, 0, 0, 1, 0, 1 ],
[ 1, 0, 0, 0, 1, 0 ],
]
SET_1 [ 0, 2, 4 ]
SET_2 [ 1, 3, 5 ]
Is bipartite
****************************************
****************************************
[
[ 0, 1, 1, 1, 0, 0 ],
[ 1, 0, 0, 1, 1, 0 ],
[ 1, 0, 0, 1, 0, 1 ],
[ 1, 1, 1, 0, 1, 1 ],
[ 0, 1, 0, 1, 0, 1 ],
[ 0, 0, 1, 1, 1, 0 ],
]
Is not bipartite
****************************************
7. Time Complexity Analysis
There are two common ways to implement the algorithm to determine whether a graph is bipartite or not. One way is using an adjacency list where an array of vertices is maintained and for each vertex, maintain a list or array of vertices that are adjacent to it. These represent the edges. This will be represented by V x E, where V is the number of vertices and E is the number of edges.
The other way is to use an adjacency matrix where an array of edges is maintained and a 1 represents that an edge exists for a pair of vertices whereas a 0 represents the absence of one. This will be a V x V matrix.
For the adjacency list, the Worst Scenario Time Complexity will be Big O ( V x E ). In using the adjacency matrix, the Time Complexity will be Big O( V x V ) or Big O( V^2 ). Big O( V x E ) in most cases will be a more efficient implementation.
8. Summary
The example in this article was implemented using the adjacency matrix. It will be left up to the reader to explore the implementation using the adjacency list.
9. Download the Source Code
You can download the full source code of this example here: How to Find If a Graph Is Bipartite?
