Python Program to Find Topological Sort

You can find a topological sort in Python using a depth-first search approach by visiting nodes and adding them to a stack after visiting all their neighbors, then reversing the stack; for example, use def topological_sort(graph): visited=set(); stack=[]; def dfs(node): visited.add(node); for n in graph[node]: if n not in visited: dfs(n); stack.append(node); for node in graph: if node not in visited: dfs(node); return stack[::-1].

Examples

Input{'A': ['C'], 'B': ['C', 'D'], 'C': ['E'], 'D': ['F'], 'E': ['H', 'F'], 'F': ['G'], 'G': [], 'H': []}

Output['B', 'D', 'A', 'C', 'E', 'H', 'F', 'G']

Input{'1': ['2'], '2': ['3'], '3': []}

Output['1', '2', '3']

Input{'X': [], 'Y': ['X'], 'Z': ['X', 'Y']}

Output['Z', 'Y', 'X']

How to Think About It

To find a topological sort, think of tasks that depend on others. We start from tasks with no dependencies, then move to tasks that depend on them. We visit each node, mark it done, and only add it to the result after all its dependencies are handled. This way, the order respects all dependencies.

Algorithm

1

Create a set to track visited nodes and a list to store the order.

2

Define a function to visit nodes recursively: mark the node visited, visit all neighbors not visited yet, then add the node to the order list.

3

For each node in the graph, if it is not visited, call the visit function.

4

Reverse the order list to get the topological sort and return it.

Code

python

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]

# Example usage
graph = {'A': ['C'], 'B': ['C', 'D'], 'C': ['E'], 'D': ['F'], 'E': ['H', 'F'], 'F': ['G'], 'G': [], 'H': []}
print(topological_sort(graph))

Output

['B', 'D', 'A', 'C', 'E', 'H', 'F', 'G']

Dry Run

Let's trace the example graph through the code

1

Start DFS from node 'A'

visited = {'A'}; call dfs on 'C'

2

Visit 'C' neighbors

visited = {'A', 'C'}; call dfs on 'E'

3

Visit 'E' neighbors

visited = {'A', 'C', 'E'}; call dfs on 'H' and 'F'

4

Visit 'H' (no neighbors)

visited = {'A', 'C', 'E', 'H'}; add 'H' to stack

5

Visit 'F' neighbors

visited = {'A', 'C', 'E', 'H', 'F'}; call dfs on 'G'

6

Visit 'G' (no neighbors)

visited = {'A', 'C', 'E', 'H', 'F', 'G'}; add 'G' to stack

7

Add 'F' and 'E' to stack after neighbors

stack = ['H', 'G', 'F', 'E']

8

Add 'C' and 'A' to stack

stack = ['H', 'G', 'F', 'E', 'C', 'A']

9

Start DFS from node 'B'

visited = {'A', 'B', 'C', 'E', 'F', 'G', 'H'}; call dfs on 'C' and 'D'

10

Visit 'D' neighbors

visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}; call dfs on 'F' (already visited)

11

Add 'D' and 'B' to stack

stack = ['H', 'G', 'F', 'E', 'C', 'A', 'D', 'B']

12

Reverse stack for result

result = ['B', 'D', 'A', 'C', 'E', 'H', 'F', 'G']

Step	Visited Set	Stack
1	{'A'}	[]
2	{'A', 'C'}	[]
3	{'A', 'C', 'E'}	[]
4	{'A', 'C', 'E', 'H'}	['H']
5	{'A', 'C', 'E', 'H', 'F'}	['H']
6	{'A', 'C', 'E', 'H', 'F', 'G'}	['H', 'G']
7	{'A', 'C', 'E', 'H', 'F', 'G'}	['H', 'G', 'F', 'E']
8	{'A', 'C', 'E', 'H', 'F', 'G'}	['H', 'G', 'F', 'E', 'C', 'A']
9	{'A', 'B', 'C', 'E', 'F', 'G', 'H'}	['H', 'G', 'F', 'E', 'C', 'A']
10	{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}	['H', 'G', 'F', 'E', 'C', 'A']
11	{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}	['H', 'G', 'F', 'E', 'C', 'A', 'D', 'B']
12	{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}	['B', 'D', 'A', 'C', 'E', 'H', 'F', 'G']

Why This Works

Step 1: Visit nodes only once

Using a visited set ensures each node is processed once, avoiding infinite loops.

Step 2: Post-order addition

Nodes are added to the stack after all their neighbors are visited, ensuring dependencies come first.

Step 3: Reverse stack for correct order

Reversing the stack gives the topological order where each node appears before nodes depending on it.

Alternative Approaches

Kahn's Algorithm (BFS)

python

from collections import deque

def kahn_topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    queue = deque([u for u in graph if in_degree[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    if len(order) == len(graph):
        return order
    else:
        return []  # Cycle detected

# Example usage
graph = {'A': ['C'], 'B': ['C', 'D'], 'C': ['E'], 'D': ['F'], 'E': ['H', 'F'], 'F': ['G'], 'G': [], 'H': []}
print(kahn_topological_sort(graph))

Uses in-degree counts and queue; detects cycles; iterative approach.

Using Python's built-in libraries (networkx)

python

import networkx as nx

g = nx.DiGraph()
g.add_edges_from([('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'E'), ('D', 'F'), ('E', 'H'), ('E', 'F'), ('F', 'G')])
order = list(nx.topological_sort(g))
print(order)

Leverages external library for convenience; requires installation; good for complex graphs.

Complexity: O(V + E) time, O(V + E) space

Time Complexity

The algorithm visits each vertex and edge once, so the time is proportional to the number of vertices plus edges, O(V + E).

Space Complexity

Extra space is used for the visited set, recursion stack, and output list, all proportional to the number of vertices and edges.

Which Approach is Fastest?

Both DFS and Kahn's algorithm run in O(V + E) time; DFS is simpler to implement recursively, while Kahn's is iterative and can detect cycles.

Approach	Time	Space	Best For
DFS-based Topological Sort	O(V + E)	O(V + E)	Simple recursive implementation
Kahn's Algorithm (BFS)	O(V + E)	O(V + E)	Cycle detection and iterative approach
networkx Library	Depends on implementation	Depends on implementation	Complex graphs and convenience