2
$\begingroup$

Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex.

I find difficult to find an explaination because Topological Sorting algorithm is applied on DAGs, whereas the other one can be applied on any type of graph, especially cyclic.

Hope my question makes sense, thank you in advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

One connection could be the following:

Given a graph $G$, construct the graph $G'$ in which every connected component of $G$ is a node, and two nodes in $G'$ have a (directed) edge if there is an edge between any two nodes in the connected components they represent in $G$.

Sometimes this graph $G'$ is known as the "supergraph" of $G$.

Now, its not hard to see why $G'$ is a DAG, and hence has a topological sort, which induces a partial ordering on $G'$.

You can "extend" this partial ordering into $G$ by saying that two nodes in the same connected component will be "the same", and two nodes from different components will relate if their respective components relate in $G'$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your kind answer. It makes sense. A topological ordering can't be performed on cyclic graphs, but if there's a cycle, then it resides entirely in the same $SCC$ $\endgroup$
    – AlessandroF
    Commented Dec 11, 2021 at 11:17
  • $\begingroup$ That is right. this is why I wrote that its possible to "extend" it. It won't result in the topological sorting, but rather with a relation that is closely related to the topological sorting $\endgroup$
    – nir shahar
    Commented Dec 11, 2021 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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