Algorithmus Topo-Sortierung
Einfache Sprache
Der Algorithmus überprüft ob es eine Topologische Sortierung für einen Digraph $D=(V,E)$ gibt. Er funktioniert folgendermaßen. Für jeden Knoten wird die Anzahl der eingehenden Kanten bestimmt. Dann werden die Knoten, welche keine eingehenden Kanten haben in einer Menge $L$ gespeichert. Es wird nun immer ein Knoten aus $L$ genommen. Für alle Knoten wo dieser Knoten hinzeigt wird die Anzahl der eingehenden Kanten um 1 reduziert. Wenn ein Knoten dadurch Null eingehende Kanten hat, wird er $L$ hinzugefügt. W
Topo-Sortierung
Entferne sukzessive Knoten mit $d_{in}(v)=0$. ührende Knoten schon abgearbeitet wurden.Dabei speicher eine Liste der aktuellen $d_{in}(v)$ Werte.
Algorithmus
1from collections import defaultdict
2
3def topological_sort(D):
4 V, E = D
5 N = 1
6 din = defaultdict(int)
7 adj_out = defaultdict(list)
8
9 # Calculate in-degrees and build adjacency list
10 for u, v in E:
11 din[v] += 1
12 adj_out[u].append(v)
13
14 # Initialize queue with nodes having 0 in-degree
15 L = [v for v in V if din[v] == 0]
16 topo = {}
17
18 while L:
19 v = L.pop(0) # Choose a node from L (FIFO queue)
20 topo[v] = N
21 N += 1
22
23 for w in adj_out[v]:
24 din[w] -= 1
25 if din[w] == 0:
26 L.append(w)
27
28 if N == len(V) + 1:
29 return (True, topo) # D is acyclic
30 else:
31 return (False, None) # D is not acyclic
Laufzeit
Laufzeit von $\mathcal O(|V|+|E|)$.