Tarjan SCC Algorithm

[don_dieguito]

Hi, Could you give me or tell me where can i find a step by step description of Tarjan's algorithm, the one which finds the strongly connected components of a directed graph ? I only know it performs a DFS (depth first search) and a vertex numbering. An applet would be suitable. Thanks.


Alex

[don_dieguito]

DFS(v) is a way for searching from the vertex v but BFS(v) is another one
(Breadth First Search). By the way, I suspect there exist mixed ways.

Diego

[Satinder]

Hi, I am a student , working on assignment "DFS and Model checking" based on Tarjan's article " Depth-First search and Linear Graph search Algos", and got stuck while implementing the same. pls send me C++ or JAVA code for Tarjan's DFS and SCC(Strongly connected components)....I'll be greatfull for that..Thank you.. Looking forward to reply

[Peter_APIIT]

No one will do the homework for you.

[SoftwareTester]

Wow, still interested in that 1972 article?
I remember studying it in the early 80s.
If I remember well the original article contains a FORTRAN implementation of it, if not you can find it for sure.
Apart from that I just Googled "Tarjan depth" and 2nd link to appear is http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
If you look at that one at the bottom you see
"Implementation of Tarjan's Algorithm in Java "

I might be old, but I've learned first to look for an answer myself.
Being a student in these days you just SHOULD have found that article yourself.
You may ask yourself the question if IT (softwaredevelopment [or making 'programs' as part of any study]) is the right choice for you

[profaar]

hi can you please send me the code to profaar@live.com

[mimi3x41]

hey
I can't get my head around tarjan alg could anyone explain how it works pls thanks