Alex Rivera | Logout

Algorithm to check if directed graph is strongly connected

Asked 2009-09-16T18:45:33.207
19

I need to check if a directed graph is strongly connected, or, in other words, if all nodes can be reached by any other node (not necessarily through direct edge).

One way of doing this is running a DFS and BFS on every node and see all others are still reachable.

Is there a better approach to do that?

Edit
Report

1 Answer

1

You can calculate the All-Pairs Shortest Path and see if any is infinite.

answered 2009-09-16T18:55:08.877

Your Answer