Topological Sort
Graph Selection
Playback Controls
Select a graph to begin topological sorting
Topological Sort Info
Requirements:
- • Must be a DAG (no cycles)
- • Directed edges only
- • Linear ordering of vertices
- • Edge u→v means u comes before v
Algorithm Comparison:
Legend:
Reference implementation of Topological Sort. Select a language tab to view and copy the code.
#include <stdbool.h>
#include <stdio.h>
#define V 6
int stack[V], top = -1;
bool visited[V];
void dfs(int graph[V][V], int v) {
visited[v] = true;
for (int i = 0; i < V; i++)
if (graph[v][i] && !visited[i])
dfs(graph, i);
stack[++top] = v; // push AFTER all descendants
}
void topological_sort(int graph[V][V]) {
for (int i = 0; i < V; i++) visited[i] = false;
for (int i = 0; i < V; i++)
if (!visited[i]) dfs(graph, i);
while (top >= 0) printf("%d ", stack[top--]);
}#include <vector>
#include <stack>
void dfs(const std::vector<std::vector<int>>& adj,
std::vector<bool>& visited, std::stack<int>& stk, int v) {
visited[v] = true;
for (int u : adj[v])
if (!visited[u]) dfs(adj, visited, stk, u);
stk.push(v);
}
std::vector<int> topologicalSort(const std::vector<std::vector<int>>& adj) {
int n = adj.size();
std::vector<bool> visited(n, false);
std::stack<int> stk;
for (int i = 0; i < n; i++)
if (!visited[i]) dfs(adj, visited, stk, i);
std::vector<int> order;
while (!stk.empty()) { order.push_back(stk.top()); stk.pop(); }
return order;
}import java.util.*;
public static List<Integer> topologicalSort(List<List<Integer>> adj) {
int n = adj.size();
boolean[] visited = new boolean[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++)
if (!visited[i]) dfs(adj, visited, stack, i);
List<Integer> order = new ArrayList<>();
while (!stack.isEmpty()) order.add(stack.pop());
return order;
}
private static void dfs(List<List<Integer>> adj, boolean[] visited,
Deque<Integer> stack, int v) {
visited[v] = true;
for (int u : adj.get(v))
if (!visited[u]) dfs(adj, visited, stack, u);
stack.push(v);
}def topological_sort(adj: list[list[int]]) -> list[int]:
n = len(adj)
visited = [False] * n
order = []
def dfs(v: int) -> None:
visited[v] = True
for u in adj[v]:
if not visited[u]:
dfs(u)
order.append(v) # add AFTER all descendants
for i in range(n):
if not visited[i]:
dfs(i)
return order[::-1] # reverse for topological orderfunction topologicalSort(adj) {
const n = adj.length;
const visited = new Array(n).fill(false);
const order = [];
function dfs(v) {
visited[v] = true;
for (const u of adj[v])
if (!visited[u]) dfs(u);
order.push(v); // push AFTER descendants
}
for (let i = 0; i < n; i++)
if (!visited[i]) dfs(i);
return order.reverse(); // reverse for topological order
}Python — Code Walkthrough
Nested dfs uses closure over order
order.append(v) # add AFTER all descendantsThe nested dfs function closes over order from the enclosing scope. Appending v after recursing into all neighbors mirrors the C stack-push approach.
Reverse at the end
return order[::-1]DFS appends in reverse finish order. Reversing the list with the [::-1] slice gives the forward topological order. This is cleaner than maintaining a stack.
Outer loop for disconnected graphs
for i in range(n): if not visited[i]: dfs(i)Every unvisited vertex seeds a new DFS. This ensures disconnected components are all included in the final order.
Recursion limit for large graphs
def dfs(v: int) -> None: visited[v] = True ...Python's default recursion limit (1000) may be hit for large DAGs. For production use, consider an iterative DFS with an explicit stack, or call sys.setrecursionlimit.