1
$\begingroup$

How can I design an algorithm using BFS(Breadth First Search) or DFS(Depth First Search) 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 approach:

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

Any idea of how to improve this solution?.

$\endgroup$
  • $\begingroup$ I am not sure that the runtime estimate is correct (or perhaps the description is incomplete). Suppose we have a complete graph of size $n$. Then we will end up running the DFS from every node. Each DFS will look at all $n$ other nodes (just to see if they have already been visited or not), so all in all we will have at least $n*n$ steps. Something more complicated would be needed to get linear time. $\endgroup$ – Carl Mummert Dec 22 '15 at 1:55
  • $\begingroup$ BFS=breadth first search, DFS=depth-first search? $\endgroup$ – Chill2Macht May 3 '16 at 5:16
1
$\begingroup$

Your solution looks good to me!

I have one suggestion if you consider directed graphs. Consider the graph:

A -> B -> C
D -> F

Let's say your algorithm starts arbitrarily at node B. It will traverse the graph through B and C and mark them as connected components - but it won't catch A!

A simple way to solve this problem is to allow the DFS to traverse the graph going both forwards and backwards, as though the graph was non-directed.

This is another way to solve it: Your algorithm produces sets of connected components. Let's say, as above, that the algorithm starts at B and produces the set {B, C}. Then, let's say that the algorithm arbitrarily selects A as its next starting point. When it traverses the graph to B, it should union the new set of connected components {A} with the already-existing set {B, C} instead of simply skipping node B.

In general, if you encounter a node that's already part of a group of connected components during a DFS, mark the set of connected components that the node is in and then skip the node. Then, when you've finished traversing as many nodes as possible without retracing paths found by previous DFS's, union all of the marked sets and the set produced by the most recent DFS into one set of connected components and discard the unioned sets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.