# Detecting strongly connected components

## Recommended Posts

johnnyk    102
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 on other sites
Flarelocke    410
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).