Sign in to follow this  

Detecting strongly connected components

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

If you intended to correct an error in the post then please contact us.

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 ) 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 this post


Link to post
Share on other sites
Traditionally, a depth first search just uses a convenient node to start with, and the results of this search is a tree. As you pointed out, this won't always get all the nodes, so then you pick a convenient one out of the remainder (nodes that have not been searched yet), and so forth. When you're done, you've got a bunch of trees (academics actually call this a forest). Then each node will have a root (the root of whichever tree it is in).

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this