Using BFS or DFS to determine the connectivity in a non connected graph?

Question

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each connected component.

This is my aproach:

1) Initialize all vertices as not visited.

2) Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn’t visit all vertices, then return false.

3) Reverse all arcs (or find transpose or reverse of graph)

4) Mark all vertices as not-visited in reversed graph.

5) Do a DFS traversal of reversed graph starting from same vertex v (Same as step 2). If DFS traversal doesn’t visit all vertices, then return false. Otherwise return true.

The idea is, if every node can be reached from a vertex v, and every node can reach v, then the graph is strongly connected. In step 2, we check if all vertices are reachable from v. In step 4, we check if all vertices can reach v (In reversed graph, if all vertices are reachable from v, then all vertices can reach v in original graph).

Any idea of how to improve this solution?.

Answer 1

How about

• let vertices = input
• let results = empty list
• while there are vertices in vertices:
  • create a set S
  • choose an arbitrary unexplored vertex, and put it in S.
  • run BFS/DFS from that vertex, and with each vertex found, remove it from vertices and add it to S.
  • add S to results
• return results

When this completes, you'll have a list of sets of vertices, where each set was made from graph searching from some vertex (making the vertices in each set connected). Assuming an undirected graph, this should work OK (off the top of my head).

Answer 2

This can be done easily using either BFS or DFS in time complexity of O(V+E).

// this is the DFS solution
numCC = 0;
dfs_num.assign(V, UNVISITED); // sets all vertices’ state to UNVISITED
for (int i = 0; i < V; i++) // for each vertex i in [0..V-1]
   if (dfs_num[i] == UNVISITED) // if vertex i is not visited yet
      printf("CC %d:", ++numCC), dfs(i), printf("\n");

The output of above code for 3 connected components would be something like :

// CC 1: 0 1 2 3 4
// CC 2: 5
// CC 3: 6 7 8