# Detecting strongly connected components

This topic is 4621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm attempting to take a graph and detect the strongly connected components of it but I'm having some difficulty understanding the descriptions of this algorithm I find online. It has been discussed before on these forums as well (here and here, mostly thanks to Ury :) So I have a directed graph, and I want to find the parts that are reliant on each other (for making a contact graph, but that shouldnt matter since its just a graph). Following the Tarjan algorithm (described here ) I should visit all the nodes of the graph in Depth First Order and record how many steps the search continues for each node. And I'm already lost, because where do I start? There is no "root" for this graph, its just a graph not a tree, and if I pick node randomly it could be a dead end, and I would miss all the other nodes. Also, the algorithm talks about each node's "root". What is a root when youre dealing with a graph? There could be multiple source nodes that have edges to a particular node. If anyone can give a brief description I would appreciate it, I'm not very familiar with graph theory and find the notation in the articles confusing, but the underlying idea seems simple if I can just get past how its explained (i'm hoping!) -John

##### Share on other sites
Quote:
 Original post by johnnykI should visit all the nodes of the graph in Depth First Order and record how many steps the search continues for each node. And I'm already lost, because where do I start? There is no "root" for this graph, its just a graph not a tree, and if I pick node randomly it could be a dead end, and I would miss all the other nodes.Also, the algorithm talks about each node's "root". What is a root when youre dealing with a graph? There could be multiple source nodes that have edges to a particular node.If anyone can give a brief description I would appreciate it, I'm not very familiar with graph theory and find the notation in the articles confusing, but the underlying idea seems simple if I can just get past how its explained (i'm hoping!)-John

First step of the algorithm is to create a new vertex x, and connect it to every other node in graph (v), by a directed connection (x, v).

Then, starting in x, you build a tree (as described in algorithm).

The algorithm then proceeds to search for nodes (roots) in this tree, for which the subtrees represent the strongly connected relation.

Note: I used this description (http://www.ics.uci.edu/~eppstein/161/960220.html#sca) of Tarjan's algorithm, so I hope I got the basics right.

##### Share on other sites
That description makes perfect sense, thank you! Couldn't say much for the 4 or 5 other descriptions I read, its all crystal clear after that one though.

Now that I know how it works, I think I'll just use the Boost graph library implementation :)

Thanks again
-John

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 26
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633694
• Total Posts
3013373
×