simp1eton's blog

Question Regarding Tarjan's Algorithm for Finding Strongly Connected Components.
By simp1eton, 14 years ago, In English
Hi all,

I have a question regarding the Tarjan's algorithm for finding strongly connected components. The Tarjan's algorithm that I am taught for finding strongly connected components is as follows:

1. Start from any arbitrary vertex.
2. DFS from that vertex. For each node x, keep two numbers, dfs_num[x] and dfs_low[x]. dfs_num[x] stores when that node is visited, while dfs_low[x] = min( dfs_low[k]) where k is all the children of x that is not the directly parent of x in the dfs-spanning tree.
3. All nodes with the same dfs_low[x] are in the same strongly connected component.

However, there seems to be a problem. Suppose the following testcase.

6 -> 5 -> 4 -> 3 -> 2 -> 1

Suppose I process the nodes in this order {1, 2, 3, 4, 5, 6}. Then, we notice that all the nodes will have dfs_low value 1, implying that all are in the same strongly connected component. Obviously that is not true.

To solve this problem, I think what needs to be done is that the dfs needs to be started from nodes with no incoming edges ie the nodes that will be the roots of the dfs-spanning tree.

However, that seems to require require much more computation. Firstly, a for loop is needed to find all nodes with no incoming edges. Then, dfs will be run from these nodes. Then, another for loop is needed to find any unvisited nodes (these nodes will be in a cycle) and dfs needs to be run again. In total, the runtime will be something like O(2*V+E).

Of course, essentially only one dfs is run (since the dfs visits different components of the graph). However, I wonder if there is an easier way to solve this problem, so that instead of breaking the dfs into two parts, only a single dfs needs to be run.

Thanks in advance!
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
If you process the nodes in this order, then for example when you run dfs(2), the vertex 1 won't be visited again and dfs_low[2] = 2.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hi adamax,

    Yep you are right. But I was wondering if there is way to do so without running more for loops, as this would seem to waste some time, although the complexity is still the same. However, suppose if E is close to V, it might be that kosaraju is faster! :O

    So is there another way without doing the V-loops?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I'm not sure I understood you right. There's no need in additional loops as you describe. It's a standard DFS.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Oh sorry, I think you meant if the nodes are processed in the order {1,2,3,4,5,6}. However, this happens:

        Visiting Node 1: dfs_num[1] = 1; dfs_low[1] = 1 as node 1 has no children
        Visiting Node 2: dfs_num[2] = 2; dfs_low[2] = dfs_low[1] = 1 as node 1 is a children of node 2 and is not a direct parent and it has dfs_low value of 1
        Visiting Node 3: dfs_num[3] = 3; dfs_low[3] = dfs_low[2] = 1 as node 2 is a children of node 2 and is not a direct parent and it has dfs_low value of 1.
        Visiting Node 4: ...

        In the end the dfs_low of all the nodes are 1.

        This is my code: http://pastebin.com/nvX7DHBv

        → Reply
        • 14 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it
          I don't understand your interpretation of dfs_low, but it seems to be different from, for example, wikipedia. dfs_low[i] is the minimum of dfs_num[k] where k is a vertex accessible from i by a path consisting of dfs-tree edges and possibly one backward edge at the end. Since the edge 2->1 is not in the dfs-tree, dfs_low[2] = 2.
          → Reply