Categories
Algorithms

Topologically Sorting a DAG

In Directed Acyclic Graphs (DAG), there are no cycles. So it is simple to find the connected components just by sorting the vertices by post-order visit number in decreasing order after one run of DFS. The run time for DFS is again O(|V|+|E|)



Leave a Reply

Your email address will not be published. Required fields are marked *