Using BFS or DFS to determine the connectivity in

问题:

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?.

回答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).

回答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

回答3:

A standard approach for solving this problem is to run DFS starting from each node.

Start by labeling all nodes as unvisited. Then, iterate over the nodes in any order. For each node, if it's not already labeled as being in a connected component, run DFS from that node and mark all reachable nodes as being in the same CC. If the node was already marked, skip it. This then discovers all CC's of the graph one CC at a time.

Moreover, this is very efficient. If there are m edges and n nodes, the runtime is O(n) for the first step (marking all nodes as unvisited) and O(m + n) for the second, since each node and edge are visited at most twice. Thus the overall runtime is O(m + n).

Hope this helps!

回答4:

Since you seem to be working with a directed graph, and you want to find the connected components (not strongly connected), you have to convert your graph to an undirected graph first. So for each vertex, add a temporary vertex in the opposite direction. Then you can use a simple DFS starting from each vertex which hasn't been visited yet to find the connected components. Finally, you can remove the temporary vertices.