0
$\begingroup$

I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am finding it surprisingly hard.

Assuming a directed acyclic graph, is it possible to simultaneously find the list of connected components while at the same time topologically sorting the nodes in each of the components?

To clarify, the output would be a list of components, where each component is a topological order of the nodes contained in that component.

Bonus points if the list of connected components is sorted following the insertion order of nodes in the graph (i.e. the first connected component will contain the first node ever inserted in the graph, regardless of global topological order; etc for subsequent components).

$\endgroup$
1
$\begingroup$

Standard algorithms for computing strongly connected components label each vertex with a number indicating which component it is part of. Then, you can use that to construct the "metagraph" of components (where each component of the graph is a vertex of the metagraph, and there is an edge $i \to j$ in the metagraph iff there is an edge $v \to w$ in the original graph where $v$ is in component $i$ and $w$ is in component $j$) in linear time. Finally, you can apply a topological sorting algorithm on the metagraph.

Some algorithms for computing strongly connected components (such as Tarjan's algorithm) already do that for you for free. Or, you can do it yourself as a postprocessing phase; since it takes only linear time, it won't increase the asymptotic running time of the algorithm.

See, e.g., https://en.wikipedia.org/wiki/Strongly_connected_component, https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm, and https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm.

$\endgroup$
  • $\begingroup$ Tarjan's algorithm seems very useful and important, but it seems I phrased my question poorly. Since I am working with a DAG, there obviously won't be any strongly connected components. In this case, Tarjan's algorithm places each node in one independent component and does not return the topological sort of the DAG. $\endgroup$ – glopes Mar 21 at 1:34
  • $\begingroup$ @glopes, if you're working with a DAG, then you don't need to compute connected components; each node is its own component of size 1. The list of vertices is already the list of connected components. All you need to do is run any standard algorithm for topological sorting. Perhaps I don't understand what you are trying to accomplish or what your situation is. $\endgroup$ – D.W. Mar 21 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.