Finding strongly connected component in a directed Graph?

1
votes

I'm following Skiena's algorithm design manual. Implementation that I'm working on is for finding Strongly connected components. However There is one statement in the book which I do not understand that is "A new strongly connected component is found whenever the lowest reachable vertex from v is v". For example take a directed graph as shown below

Directed Graph with Connected component

Here above statement is true for vertex "V3" and will give us strongly connected component but this statement is also true for V2 which do not give us any strongly connected component.

My question is how does above statement always holds true ?

1
algorithmgraph
But V2 is not reachable from V2. - perreal
Can you post the algorithm? There are different ways to find SCCs, and most of us probably don't have the text book handy. - Bernhard Barker
What makes you think V2 isn't a strongly connected component all by itself? - Bernhard Barker
@Dukeling because from V2 we can reach V3 but we can't go back, I think for a strongly connected components directed paths exist between all pairs of vertices. - naveen
@naveen The book presumably says something about not revisiting vertices or edges or removing vertices or edges after they've been processed, in which case V3 is no longer reachable from V2, thus V2 is the lowest reachable vertex from V2, thus we found an SCC, which is just V2. - Bernhard Barker

1 Answers

0
votes

I can't tie this up with my (first) version of Skienna's algorithm design manual, but if this is the algorithm I think it is (http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm), this is the second part of a two-part algorithm, and the effect of the first part is that in your diagram there will be a depth first search from V3, removing that component, before one from V2, and only then will there be a depth first search from V1.

The first part runs successive depth-first searches, and numbers the nodes in order of the last time they are visited by the depth first search. The second part, which you are describing, initiates depth first searches in decreasing order of the number assigned, and the edges between nodes are reversed.

If A can get to B, but B cannot get to A, then if the first part visits A before B it will visit B in that depth first search and number A greater than B, because it exits A after exiting B. If it visits B before A it will number A greater than B as well, because it will not get to A from B and so will visit A in a later depth first search.

So if A can get to B but B cannot get to A, then in the second pass (with edges reversed) B can get to A but A cannot get to B. It will start from A and output its strong component and then only later start from B and output its strong component.