forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtopological_sort_bfs.py
More file actions
65 lines (46 loc) · 1.6 KB
/
topological_sort_bfs.py
File metadata and controls
65 lines (46 loc) · 1.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
"""
Topological Sort (Kahn's Algorithm / BFS)
Computes a topological ordering of a directed acyclic graph. Raises
ValueError when a cycle is detected.
Reference: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
Complexity:
Time: O(V + E)
Space: O(V + E)
"""
from __future__ import annotations
from collections import defaultdict, deque
def topological_sort(vertices: int, edges: list[tuple[int, int]]) -> list[int]:
"""Return a topological ordering of the vertices.
Args:
vertices: Number of vertices (labelled 0 .. vertices-1).
edges: Directed edges as (u, v) meaning u -> v.
Returns:
List of vertices in topological order.
Raises:
ValueError: If the graph contains a cycle.
Examples:
>>> topological_sort(3, [(0, 1), (1, 2)])
[0, 1, 2]
"""
graph: dict[int, list[int]] = defaultdict(list)
in_degree = [0] * vertices
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue: deque[int] = deque()
for i in range(vertices):
if in_degree[i] == 0:
queue.append(i)
sorted_order: list[int] = []
processed = 0
while queue:
node = queue.popleft()
sorted_order.append(node)
processed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if processed != vertices:
raise ValueError("Cycle detected, topological sort failed")
return sorted_order