🌵
Christian's Wiki
/
📖
Data Structures & Algorithms
/
Algorithm
/
Connected Components

Connected Components

‣
Graph Theory: What is a connected component in an undirected graph? How would you find connected components?

We simple need to do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components. Below are steps based on DFS.

Pseudocode:

  1. Initialize all vertices as not visited.
  2. Do following for every vertex 'v'. (a) If 'v' is not visited before, call DFSUtil(v) (b) Print new line character

DFSUtil(v)

  1. Mark 'v' as visited.
  2. Print 'v'
  3. Do following for every adjacent 'u' of 'v'. If 'u' is not visited, then recursively call DFSUtil(u)
‣
What is it?

A connected component of an undirected graph is a maximal set of nodes such that each pair of nodes is connected by a path.

‣
How to find?
❗
In DFS(G), initialize count = 0 and increment for every DFSUtil() call
image
‣
Applications