19

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.

Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
user2738777
  • 418
  • 1
  • 5
  • 21
  • 3
    What do you mean by the intersection of two subgraphs? As far as I know a bipartite graph is a graph whose vertices can be partitioned into two sets with all the edges starting in one set and ending in another. – biziclop May 27 '15 at 15:38
  • 5
    As for the BFS, you can start from one vertex, colour it blue, then colour all its neighbours red, then go through the neighbours' neighbours and colour them all blue again and so on. If you encounter a node already coloured and it's a different one than you need to set, the graph isn't bipartite. – biziclop May 27 '15 at 15:41
  • @biziclop I meant the same. two sets are the two subgraphs and intersection is a NULL set which supports the biparity that a vertex can not be in two sets at the same time.If it is then it is not a bipartite graph. – user2738777 May 27 '15 at 15:44
  • 4
    @user2738777 You can bipartition any vertex set into two disjoint sets, a graph is only bipartite if you can do that without having an edge that runs between two vertices of the same partition set. – G. Bach May 27 '15 at 16:55

7 Answers7

34

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 .

Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
  • 3
    What if the graph is not connected? – Edward Doolittle May 27 '15 at 16:05
  • 1
    @shekharsuman your comment is wrong. a graph w/o edges is vacuously bipartite, sine every edge in it answers the condition of being connected to both components. – amit May 27 '15 at 16:12
  • 1
    @EdwardDoolittle You only need each connected component to be bipartite, and then the union of them is also bipartite., – amit May 27 '15 at 16:18
  • 1
    Of course ... but the possibility of unconnected components needs to be reflected in the algorithm. I don't see provision for unconnected components in the proposed algorithm. – Edward Doolittle May 27 '15 at 17:34
  • 1
    @shekharsuman: The problem is that the algorithm you have described is *not* a general algorithm to detect bipartiteness, *because* it fails on graphs with more than one component. -1 until you update your (otherwise very good) answer to address this. – j_random_hacker May 27 '15 at 18:58
  • 1
    Given the nature of the question it is a reasonable assumption that we already established that the graph is connected. But in general you'd have to cater for that. – biziclop May 27 '15 at 20:03
  • 1
    Your edits don't quite make the most important point, which is that a graph is bipartite if and only if each of its connected components can be proven to be bipartite using the algorithm you originally described. – j_random_hacker May 29 '15 at 23:49
  • This is very late, but how do you know which root to choose? Do you have to check all possible roots in all components? What do you do with an undirected graph? – synchronizer Feb 10 '17 at 23:54
  • @synchronizer - Probably, this would help in the clarification of your question -> https://lucatrevisan.wordpress.com/2011/02/23/cs261-lecture14-algorithms-in-bipartite-graphs/ – Am_I_Helpful Feb 11 '17 at 17:47
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.

Xceptional
  • 65
  • 7
1

The following is a BFS approach to check whether the graph is bipartite.

  • c = 0
  • pick a node x and set x.class = c
  • let ys be the nodes obtained by BFS
    • c = 1-c
    • for y in ys set y.class = c
    • if any y in ys has a neighbour z with z.class == c then the graph is not bipartite
    • repeat until no more nodes are found
  • the graph is bipartite

This assumes that the graph is a single connected component -- if it is not, simply do this procedure for each component.

mitchus
  • 4,677
  • 3
  • 35
  • 70
1

Here is a Prolog CLP(FD) solution. Just model each edge in the graph as a variable in the domain 0..1. Then model each vertex as an equation:

X #\= Y.

Then issue labeling. If the labeling finds a solution, you are done. It might find multiple solutions though. Here is a run for your example:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam

:- use_module(library(clpfd)).
problem(L) :- L=[A,B,C,D,E,F,G],
    A #\= E, A #\= F,
    B #\= E,
    C #\= E, C #\= F, C #\= H,
    D #\= G, D #\= H,
    E #\= A, E #\= B, E #\= C,
    F #\= A, F #\= C, F #\= G,
    G #\= F, G #\= D,
    H #\= C, H #\= D.

?- problem(L), L ins 0..1, label(L).
L = [0, 0, 0, 1, 1, 1, 0] ;
L = [1, 1, 1, 0, 0, 0, 1].

Works also in GNU Prolog, SICStus Prolog, Jekejeke Minlog etc.. mostly with any Prolog system that implements CLP(FD). Alternatively could also use CLP(B) or dif/2.

1

Make a bfs Tree.If there are edges between the vertexes of the same level of tree.Then the graph is non bipartite,else it is bipartite.

ashu beckham
  • 21
  • 1
-1

you can refer this link as given below
this code contains Check whether a given graph is Bipartite or not using BFS Algorithm
https://github.com/gangwar-yogendra/Graph/blob/master/BipartiteGraphUsingBFS.c

Yogendra Kumar
  • 113
  • 1
  • 8
  • 2
    While this link may contain the answer, it's always best to add the answer here aswell. Overtime links might get broken – ThomasVdBerge Apr 30 '18 at 21:19
-2

Do it more simpler way.

Run the strongly connected component algorithm.

If any node of metagraph obtained has more than two vertices then the given graph is not bipartite.

Gaurav Aggarwal
  • 9,809
  • 6
  • 36
  • 74
Gurman SIngh
  • 1