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.
Taken from GeeksforGeeks
Following is a simple algorithm to find out whether a given graph is Birpartite or not using Breadth First Search (BFS) :-
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 .