http://code.activestate.com/recipes/tags/directed-oriented/2013-04-03T19:30:32-07:00ActiveState Code Recipes2013-04-03T19:30:32-07:00Mark Dickinsonhttp://code.activestate.com/recipes/users/4172683/http://code.activestate.com/recipes/578507-strongly-connected-components-of-a-directed-graph/

<p style="color: grey"> Python recipe 578507 by <a href="/recipes/users/4172683/">Mark Dickinson</a> (<a href="/recipes/tags/connected/">connected</a>, <a href="/recipes/tags/directed/">directed</a>, <a href="/recipes/tags/graph/">graph</a>, <a href="/recipes/tags/strong/">strong</a>, <a href="/recipes/tags/tarjan/">tarjan</a>). Revision 3. </p> <p>Two linear-time algorithms for finding the strongly connected components of a directed graph. <code>strongly_connected_components_tree</code> implements (a variant of) Tarjan's well-known algorithm for finding strongly connected components, while <code>strongly_connected_components_path</code> implements a path-based algorithm due (in this form) to Gabow.</p> <p>Edit: I added an iterative function <code>strongly_connected_components_iterative</code>; this is a direct conversion of <code>strongly_connected_components_path</code> into iterative form. It's therefore safe to use on high-depth graphs, without risk of running into Python's recursion limit.</p>