graph theory question
Posted: Mon Jul 08, 2002 9:07 am
what is the best algorithms to find all strongly connected component of a graph ? I only know the trivial one in text book with time O(V * (E+v)) or O(V^3).
Thanks
Thanks
Page 1 of 1
Posted: Mon Jul 08, 2002 11:12 am
That would be Tarjan's algorithm. It consists of just two depth-first searches, giving a running time of O(n+m)
Posted: Mon Jul 08, 2002 1:01 pm
thanks, it said O(n) to determine strongly connected components. Looks great 