Skip to main content

Topological Sort

topological-sort

Solved using Postorder DFS.

  • For every node in graph, perform postorder dfs and keep appending the resulant path to the solution.
  • Postorder means, childrens will be evaluated before parents - so we will need to reverse the result

Wait! Randomly picking some nodes, running dfs to get a path, and concatenating these paths would magically result in a topologically ordered nodes?

In the above graph, lets say we perform DFS from nodes {D, E, F}

topological-sort

topological-sort

topological-sort

Summary (ChatGpt)​

  • Randomly picking nodes: The DFS starts from any unvisited node, which can seem random initially.
  • Running DFS to get a path: Each DFS run processes a path of nodes, ensuring all dependencies are met before a node is fully processed.
  • Concatenating these paths: The stack collects nodes from all DFS runs, maintaining the correct order due to postorder processing.

The DFS approach systematically ensures that each node is processed after all its dependencies, resulting in a correct topological order when the stack is reversed. This method leverages the properties of DFS and postorder traversal to achieve a valid topological sort.