We have been given an undirected graph with n nodes and m edges. We are required to find all the connected components in it.

__ __

__Connected components :-__

• A connected component consist a group of nodes in which each node can be reached from any other node of the respective connected component. In simple words a connected component consists of set of nodes in a undirected graph that are linked to each other by paths.

• No path exists between two different connected components.

• In the above shown graph there are three connected components :-

1. First connected component consists of node 1 -> 2 -> 3 as they are linked to each other.

2. Second connected component consists of node 4 -> 5 as they are linked to each other.

3. Third connected component consist a single node 6 as no other node is linked to it.

__Algorithm used:-__

__ __

We can solve this problem with different methods :-

• Using Depth First Search (DFS)

• Using Breadth First Search (BFS)

__ __

__ __

__ __

• We will be doing a series of DFS to solve this problem.

• Firsty we will iterate over all the nodes and check whether the node is visited or not (Initially all the nodes are unvisited).

• If a node is unvisited then we will perform DFS over that particular node which will result in traversing of all the nodes which are connected to it and marking them as visted. After which we will check for the next unvisited node and perform the DFS on it, and the same process goes on.

• Time complexity of this algorithm : **O(N+M)**

where N -> No of nodes in the graph

M -> No of edges in the graph

__Implementation :-__

__Input :-__

6 4

1 2

2 3

3 1

4 5

__Output :-__

1 2 3

4 5

6

Total number of components : 3

__ __

__ __

• This algorithm is similar to the previous one with a small difference that here we use BFS for traversing the graph instead of DFS.

• Time complexity of this algorithm : **O(N+M)**

where N -> No of nodes in the graph

M -> No of edges in the graph

__Implementation :-__

__Input :-__

6 4

1 2

2 3

3 1

4 5

__Output :-__

1 2 3

4 5

6

Total number of components : 3

It is highly recommended to solve below problems, they are handpicked by Programmers Army:

__Practice Problems :-__

This article is contributed by Shaan Kumar

So that’s it for this article we will be coming up with our next article on further topics of Graph Theory very soon till then keep learning, keep coding, keep reading and keep improving !!

**Happy Coding **

**By Programmers Army **
**😊**