Home » Core Java » How to find a Bipartite Graph? Frank holds a Bachelor of Science in Biology from The City University of New York (The City College of New York) and a Bachelor of Arts in Computer Science from The City University of New York (Hunter College). As an undergraduate, he had taken courses where programs were written in Fortran, Basic, Pascal, COBOL, and Assembly Language for the IBM 4341 Mainframe. He has been a software developer for over 30 years having built desktop apps, mobile apps and web apps. He has built software in C/C++, VisualBasic, TCL, Java, PHP, XML/XSLT, Perl, Shell Scripting and Python. Frank was also an educator in The City University of New York (Borough of Manhattan Community College, New York City College of Technology) having taught courses in Pascal, VisualBasic, C++ for over 10 years. Finally, he has recently helped students create programs in Lisp, R, Masm, Haskell, Scheme and Prolog.

# How to find a Bipartite Graph?

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.

## 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++) {
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++) {
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;

while(al.size() > 0 && rv) {
int u = al.get(0);
al.remove(0);

for(int v = 0; v < setAssignment.length; v++) {
if (setAssignment[v] == UNASSIGNED) {
if(setAssignment[u] == SET_1)
setAssignment[v] = SET_2;
else if(setAssignment[u] == SET_2)
setAssignment[v] = SET_1;
} else if(setAssignment[v] == setAssignment[u]) {
rv = false;
break;
}
}
}
if (al.size() == 0) {
if (nextUnassigned(setAssignment) >= 0) {
index = nextUnassigned(setAssignment);
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++) {
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) {

// 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}
},
};
System.out.println(repeat("*", 40));

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

You can download the full source code of this example here: How to Find If a Graph Is Bipartite?

# Do you want to know how to develop your skillset to become a Java Rockstar?

## Subscribe to our newsletter to start Rocking right now!

### and many more .... 