Kahns Algorithmus: Topologische Sortierung mit BFS
Berechnen Sie die Eingangsgrade aller Knoten, stellen Sie Knoten mit Eingangsgrad null in eine Warteschlange und verarbeiten Sie diese, um eine topologische Reihenfolge zu erzeugen und Zyklen zu erkennen.
Kahns Algorithmus: Topologische Sortierung mit BFS ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist eine topologische Sortierung?
Eine topologische Sortierung eines gerichteten azyklischen Graphen (DAG) ist eine Anordnung seiner Knoten, bei der jede gerichtete Kante u → v bedeutet, dass u in der Anordnung vor v kommt. Sie stellt eine gültige Ausführungsreihenfolge für Aufgaben mit Abhängigkeiten dar – etwa in Build-Systemen, bei der Kursplanung oder bei der Paketverwaltung. Nur DAGs besitzen gültige topologische Anordnungen; ein Zyklus macht dies unmöglich.
Kahn-Algorithmus: Grundidee
Der Kahn-Algorithmus ist ein BFS-basierter Ansatz für die topologische Sortierung. Die zentrale Erkenntnis: Ein Knoten mit Eingangsgrad 0 (ohne Voraussetzungen) kann an die erste Stelle der Anordnung gesetzt werden. Entfernen Sie ihn anschließend und verringern Sie den Eingangsgrad seiner Nachbarn. Neue Knoten mit Eingangsgrad 0 werden verfügbar. Wiederholen Sie dies, bis alle Knoten platziert sind oder ein Zyklus erkannt wird (Knoten mit einem von null verschiedenen Eingangsgrad bleiben übrig).
Berechnung der Eingangsgrade
Erstellen Sie zunächst die Adjazenzliste und berechnen Sie den Eingangsgrad (die Anzahl eingehender Kanten) für jeden Knoten. Knoten mit Eingangsgrad 0 sind die Startpunkte – sie haben keine Abhängigkeiten. Für einen Graphen mit den Kanten [(0,1),(0,2),(1,3),(2,3)] lauten die Eingangsgrade: 0→0, 1→1, 2→1, 3→2. Nur Knoten 0 startet mit Eingangsgrad 0.
from collections import deque, defaultdict
def compute_in_degree(n, edges):
in_degree = [0] * n
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
return graph, in_degree
graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind) # [0, 1, 1, 2]Implementierung des Kahn-Algorithmus
Reihen Sie alle Knoten mit Eingangsgrad 0 in eine Warteschlange ein. Verarbeiten Sie jeden Knoten: Fügen Sie ihn zum Ergebnis hinzu, verringern Sie anschließend für jeden Nachbarn den Eingangsgrad und reihen Sie den Nachbarn ein, wenn dieser 0 erreicht. Wenn die Ergebnisliste weniger Knoten als der Graph enthält, existiert ein Zyklus – einige Knoten konnten nie aus der Warteschlange entfernt werden.
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
if len(order) == n:
return order # valid topological sort
return [] # cycle detected
print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Zyklenerkennung mit Kahn
Der Kahn-Algorithmus bietet eine Zyklenerkennung ohne zusätzlichen Aufwand: Wenn len(order) < n gilt, wurden einige Knoten nie in die Warteschlange aufgenommen, weil ihr Eingangsgrad nie 0 erreicht hat – sie sind Teil eines Zyklus. Das ist übersichtlicher als die Verwaltung eines farbcodierten Besucht-Arrays. Geben Sie eine leere Liste zurück, um anzuzeigen, dass ein Zyklus existiert.
# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result) # [] (cycle detected)
# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result) # [0, 1, 2]Zeit- und Speicherkomplexität
Der Kahn-Algorithmus verarbeitet jeden Knoten einmal (er wird einmal aus der Warteschlange entfernt) und jede Kante einmal (der Eingangsgrad wird einmal verringert). Zeitkomplexität: O(V + E). Speicherbedarf: O(V + E) für die Adjazenzliste und das Eingangsgrad-Array sowie O(V) für die Warteschlange. Das ist optimal – um eine gültige Anordnung zu erstellen, müssen Sie mindestens alle Knoten und Kanten lesen.
Lexikografisch kleinste topologische Anordnung
Der Kahn-Algorithmus erzeugt mit einem Min-Heap statt einer Warteschlange die lexikografisch kleinste topologische Anordnung. Ersetzen Sie deque durch heapq: Fügen Sie (node) ein und verarbeiten Sie immer zuerst den kleinsten verfügbaren Knoten. Dadurch wird unter allen möglichen topologischen Sortierungen garantiert die lexikografisch kleinste gültige Anordnung gewählt.
import heapq
from collections import defaultdict
def kahn_lex_order(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
node = heapq.heappop(heap)
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
heapq.heappush(heap, nxt)
return order if len(order) == n else []
print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))Anwendung: Course Schedule I
Course Schedule (LeetCode 207): Gegeben sind n Kurse und Voraussetzungen. Können Sie alle Kurse abschließen? Modellieren Sie die Voraussetzungen als gerichtete Kanten und prüfen Sie, ob eine gültige topologische Sortierung existiert (also kein Zyklus vorhanden ist). Geben Sie True zurück, wenn der Kahn-Algorithmus eine Anordnung der Länge n erzeugt, und False, wenn ein Zyklus erkannt wird.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites: # b must be taken before a
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)Anwendung: Course Schedule II
Course Schedule II (LeetCode 210): Geben Sie die tatsächliche Reihenfolge zurück, in der die Kurse belegt werden sollen. Gehen Sie wie oben vor, geben Sie aber statt eines booleschen Werts die Liste order zurück. Wenn ein Zyklus existiert, geben Sie eine leere Liste zurück. Die Ausgabe des Kahn-Algorithmus wird dabei direkt als Antwort verwendet.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Parallele Aufgabenplanung
Eine fortgeschrittenere Anwendung: Gegeben sind Aufgaben mit Abhängigkeiten. Finden Sie die minimale Anzahl von Runden, die benötigt wird, wenn Aufgaben ohne Abhängigkeiten parallel ausgeführt werden können. Verarbeiten Sie den Kahn-Algorithmus Ebene für Ebene (ähnlich der Ebenenverarbeitung bei BFS): Reihen Sie alle Knoten mit Eingangsgrad 0 ein, verarbeiten Sie die gesamte aktuelle Warteschlange als eine Runde und reihen Sie anschließend die neu freigegebenen Knoten als nächste Runde ein. Zählen Sie die Runden.
from collections import deque, defaultdict
def min_rounds(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
rounds = 0
while queue:
rounds += 1
for _ in range(len(queue)): # process current level
node = queue.popleft()
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return rounds
print(min_rounds(4, [(0,2),(1,2),(2,3)])) # 3Topologische Sortierung und DP auf DAGs
Die topologische Sortierung ermöglicht dynamische Programmierung auf DAGs: Verarbeiten Sie die Knoten in topologischer Reihenfolge. Beim Berechnen von dp[v] sind die Werte aller Vorgänger dp[u] bereits endgültig. So lässt sich die topologische Sortierung mit DP für Probleme wie den längsten Weg in einem DAG, die minimalen Kosten zum Erreichen aller Knoten oder den maximalen Gewinn aus einer Abhängigkeitskette kombinieren. Die Reihenfolge garantiert, dass der DP-Wert jedes Knotens genau einmal berechnet wird, nachdem alle seine Abhängigkeiten verarbeitet wurden.
from collections import deque, defaultdict
def longest_path_dag(V, edges):
graph = defaultdict(list)
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
queue = deque(i for i in range(V) if in_degree[i] == 0)
dp = [0] * V
while queue:
u = queue.popleft()
for v, w in graph[u]:
dp[v] = max(dp[v], dp[u] + w)
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return max(dp)
print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)])) # 7Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion im Bereich Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Der Kahn-Algorithmus berechnet die topologische Sortierung, indem er per BFS wiederholt Knoten mit Eingangsgrad 0 entfernt, die Zyklenerkennung erfolgt ohne zusätzlichen Aufwand – wenn len(order) < n gilt, existiert ein Zyklus, und das Ersetzen der Warteschlange durch einen Min-Heap liefert die lexikografisch kleinste topologische Anordnung. Als Nächstes untersuchen wir die DFS-basierte topologische Sortierung in Postorder als Alternative zum Kahn-Algorithmus.
Häufig gestellte Fragen
Ist die Lektion „Kahns Algorithmus: Topologische Sortierung mit BFS“ kostenlos?
Ja — der vollständige Text von „Kahns Algorithmus: Topologische Sortierung mit BFS“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Kahns Algorithmus: Topologische Sortierung mit BFS“?
Berechnen Sie die Eingangsgrade aller Knoten, stellen Sie Knoten mit Eingangsgrad null in eine Warteschlange und verarbeiten Sie diese, um eine topologische Reihenfolge zu erzeugen und Zyklen zu erke… Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Kahns Algorithmus: Topologische Sortierung mit BFS“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Kahns Algorithmus: Topologische Sortierung mit BFS
- Topologische Sortierung per DFS-Postorder
- Course Schedule I und II
- Stark zusammenhängende Komponenten mit Kosaraju