Question

Bipartite graph is a graph, which vertices can be partitioned into 2 parts - so that all edges connect only vertices from different parts. For example, this is a bipartite graph where one part has 3 vertices (a,b,c), and the other part - 4 vertices (d.e.f.g). Note there are NO edges in-between vertices coming from the same part. a b d f e g Give the order in which nodes are traversed with BFS. After listing a node, add its BFS-label in parenthesis. from source a: a(0). from source d: d(0), What similarity do you notice between BFS labels for each of two parts (remember, graph is bipartite), in each of two cases when you run BFS algo from two different courses? Refer to slides for a hint if you get stuck. How one could determine with BFS algorithm, whether given graph is bipartite or not? This graph above is bipartite. For example of a graph which is not refer to example from slides/video where we performed BFS algorithm in details.

Answer 1

BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

Now from the given bipartite graph, let's start the BFS traversal.

From source a:

1. From a, we have two children i.e d and f. So let's explore d

a-->d

2. d has only one children i.e b, so take b in.

a --> d --> b

3. Now come back to a and explore other children of a i.e f.

a --> d --> b --> f

4. f has two children a and c. SInce a has been discovered so take c in

a --> d --> b --> f --> c

5. c has two children i.e e and g and both are leaf nodes. So take both in

a --> d --> b --> f --> c --> e --> g

Hence, the BFS traversal here is

a --> d --> b --> f --> c --> e --> g

From source d:

1. d has two children a and b. So let's take b first

d --> b

2. Then return to a and discover the other children i.e a

d --> b --> a

3. a has two children d and f. since d has been discovered so take f in

d --> b --> a --> f

4. f has two children i.e a and c. SInce a is discovered to so take c in.

d --> b --> a --> f --> c

5. Now c has two children i.e e and g and both are leaf nodes. So take both in

d --> b --> a --> f --> c --> e --> g

Hence, the BFS traversal here is

d --> b --> a --> f --> c --> e --> g

- The similarity between the both BFS traversals is that after the 3 nodes traversal, rest of the nodes traversal is all same.

- In BFS algorithm, In general, when the bfs reaches a node, you go through its neighbours and check if any of them is already visited and on the same side as your node is. Then, the graph is not bipartite. If you reach the end of the bfs with no errors, then the graph is bipartite.