How to find if a graph is bipartite?

Question

I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union is graph G. I am trying to find if a graph is bipartite or not using BFS. Still it is not clear to me that how can we find this using BFS.

Let us say we have graph defined as below.

a:e,f
b:e
c:e,f,h
d:g,h
e:a,b,c
f:a,c,g
g:f,d
h:c,d

What i need here is step by step explanation of how this graph is a bipartite or not using BFS.

Answer 1

Taken from GeeksforGeeks

Following is a simple algorithm to find out whether a given graph is Birpartite or not using Breadth First Search (BFS) :-

1. Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite).

A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.

Also, NOTE :-

-> It is possible to color a cycle graph with even cycle using two colors.

-> It is not possible to color a cycle graph with odd cycle using two colors.

EDIT :-

If a graph is not connected, it may have more than one bipartition. You need to check all those components separately with the algorithm as mentioned above.

So, for various disconnected sub-graph of the same graph, you need to perform this bipartition check on all of them separately using the same algorithm discussed above. All of those various disconnected sub-graph of the same graph will account for its own set of bipartition.

And, the graph will be termed bipartite, IF AND ONLY IF, each of its connected components are proved to be bipartite .

Answer 2

From Carnegie Mellon University:

"Recall that a graph G = (V, E) is said to be bipartite if its vertex set V can be partitioned into two disjoint sets V1, V2 such that all edges in E. have one endpoint in V1 and one endpoint in V2.

(source: http://www.cs.cmu.edu/~15251/homework/hw5.pdf)

Are you sure that you need to use BFS? Determining if a graph if bipartite requires detecting cycle lengths, and DFS is probably better for cycle detection than BFS.

Anyway, a graph if bipartite if and only if it has no cycles of odd length. If you're allowed to use DFS, you can DFS on the graph and check for back-edges to detect the presence of cycles and use DFS timestamps to compute the size of each cycle.