DFS Topological Sort
Learn DFS Topological Sort (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Topological Sort via DFS Finishing Order Run DFS from every unvisited vertex; when a vertex FINISHES (all its descendants fully explored), push it onto a stack. Reversing the finish order (via the stack) gives a valid topological order - a vertex finishes AFTER everything reachable from it, so it naturally ends up appearing BEFORE those descendants once reversed.
More lessons in Graphs
- Graph Representation - Adjacency Matrix
- Graph Representation - Adjacency List
- Directed Graph
- Undirected Graph
- Weighted Graph
- BFS
- DFS
- Connected Components
- Cycle Detection
- Bipartite Graph
- Topological Sort
- Kahn's Algorithm
- Shortest Path - BFS
- Shortest Path - Dijkstra
- Shortest Path - Bellman-Ford
- Shortest Path - Floyd-Warshall
- Minimum Spanning Tree - Prim's
- Minimum Spanning Tree - Kruskal's
- Disjoint Set Union - DSU
- Union-Find
- Strongly Connected Components - Kosaraju
- Strongly Connected Components - Tarjan
- Bridges
- Articulation Points
- Euler Path / Circuit
- Hamiltonian Path / Cycle
- Graph Coloring
- Network Flow
- Maximum Flow
- Bipartite Matching