Connected Component and Cycle Detection using Breadth First Search

Hi, all welcome to Session 5. Things to be discussed here.

• Finding Connected Component using BFS
• Cycle Detection in Graph using BFS
• Practice Problem

This particular discussion is based on the "Application of Breadth-first Search Algorithm". Today we will be looking into two problems and implementing the BFS concept to solve those problems. And yes, and these problems can also be solved by using Depth-first Search which we have discussed in the earlier session. So let us start with the first thing first.

Finding Connected Component using BFS

From the earlier session, we know that BFS is a graph traversal algorithm and to find all the connected components we need to traverse whole the graph. To understand this let us take an example

Fig 1: Graph with 14 vertices

• In the above graph, we are having 14 vertices which are not all connected ( Meaning between any two pair of vertices we do not have path ).
• Eg. if we want to go from nodes 1 to 7 then we will not be able to go as there is no path which means 7 is disconnected from 1 and vice-versa.
• For real-world example let us suppose all the vertices to denote a city and edges to be bidirectional roads. Then if a person wants to go from city 1 to city 7 then he/she will not be able to go as there are no roads which connect city 1 and 7.
• Now BFS can traverse all the connected vertices in one run ie. if we set source node to be 1 then it can traverse these { 1, 2, 3, 4 } nodes and other nodes will remain unvisited.
• Or if we select node 7 as source node then it can traverse these { 7, 9, 5, 6, 11, 10, 8 } nodes and others will remain unvisited.
• So in order to traverse the whole graph here, we need to run the BFS algorithm to 3 times and hence number of the connected components will be 3.
• The same concept we have used in finding the number of the connected components using DFS, ie. number of times we run DFS that many connected components will be there.

Implementation

Cycle Detection in a Graph using DFS

We know that if we have two or more distinct path between a pair of vertices then there exist a Cycle in a Graph. To understand this more clearly we will take a simple example

Fig 2: Connected Graph

• In the Fig 2 graph, we are having 6 nodes in which all are connected by one or many paths.
• For example, let us take two nodes 1 and 5 and list the nodes which are in the path from 1 to 5.
• First path: 1 -> 3 -> 5
• Second path: 1 -> 2 -> 4 -> 3 -> 5
• Now here we are getting two distinct paths why? ( Because of cycle 1-> 2 -> 4 -> 3 ->1)
• This is because when we do BFS traversal to each vertex v where u is the adjacent vertex and u is already visited and u is not the parent of v ( that is it got visited by some vertices earlier ) then there is a cycle.
• Here, the adjacency list of the above graph is like this
• 1 -> 2 -> 3
• 2 -> 1 -> 4
• 3 -> 1 -> 4 -> 5
• 4 -> 2 -> 3
• 5 -> 3 -> 6
• 6 -> 5
• Now run BFS from vertex 1 as the source node, it will visit 2  and 3.  Then vertex 2 will become source node and will visit 4, then 3 will become the source and will visit 4 but 4 is already visited earlier by 2 and 3 is not a parent of 4 ( ie. through which 4 is visited earlier )  hence there is a cycle.

Implementation

Practice Problem

1. Cyclic Component ( 977E )
2. Infinite Path ( 1327D )
3. Jeremy Bearimy ( 1280C )
4. Maximum White Subtree ( 1324F )
5. Wires ( 1250N )

That's all for this article, in the next article we will be discussing Introduction to Tree, Tree Traversal, Diagonal of Tree and problems related to them. Before moving to the next session do practice the above problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you ).

If you have some content OR material or want to add something related to this then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA