Topologische Sortierung mit Kahns Algorithmus
Ordnen Sie Aufgaben, die voneinander abhängen
Topologische Sortierung mit Kahns Algorithmus 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 eine topologische Sortierung ist
Eine topologische Sortierung listet jeden Knoten eines gerichteten Graphen so auf, dass jede Kante von einem früheren zu einem späteren Knoten zeigt. Denken Sie an Aufgaben, die vor den Aufgaben erledigt werden müssen, die von ihnen abhängen.
Nur DAGs sind möglich
Das funktioniert nur bei einem DAG, also einem gerichteten azyklischen Graphen. Wenn ein Zyklus existiert, kann keine gültige Reihenfolge alle Abhängigkeiten erfüllen.
Die Idee des Eingangsgrads
Kahns Algorithmus beruht auf dem Eingangsgrad: der Anzahl der Kanten, die in einen Knoten zeigen. Ein Knoten mit Eingangsgrad null hat keine unerfüllten Abhängigkeiten.
Jeden Eingangsgrad zählen
Im ersten Durchlauf gehen Sie alle Kanten durch und zählen, wie oft jeder Knoten als Ziel vorkommt. Dadurch erhalten Sie den Eingangsgrad jedes Knotens.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Die Bereitschaftswarteschlange füllen
Jeder Knoten mit Eingangsgrad null ist sofort bereit. Fügen Sie daher alle solchen Knoten zu Beginn in eine Warteschlange ein.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Einen Knoten verarbeiten
Entnehmen Sie einen bereiten Knoten und fügen Sie ihn Ihrer Reihenfolge hinzu. Das ist jetzt sicher, weil für ihn keine unerfüllten Abhängigkeiten mehr bestehen.
u = q.popleft()
order.append(u)Seine Nachbarn freigeben
Verringern Sie bei jedem Nachbarn den Eingangsgrad um eins. Sobald ein Nachbar null erreicht, ist er bereit und kommt in die Warteschlange.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Wiederholen, bis die Warteschlange leer ist
Entnehmen Sie weiterhin Knoten und geben Sie ihre Nachbarn frei, bis die Warteschlange leer ist. Die Reihenfolge wächst dabei Knoten für Knoten, bis jeder Knoten platziert wurde.
Einen Zyklus gleich mit erkennen
Wenn Ihre endgültige Reihenfolge weniger als n Knoten enthält, hat ein Zyklus den Rest blockiert. Kahns Algorithmus erkennt Zyklen ohne zusätzlichen Aufwand.
if len(order) < n:
print('cycle exists')Die Laufzeit
Jeder Knoten und jede Kante wird einmal verarbeitet, daher läuft Kahns Algorithmus in O(V + E). Damit eignet er sich auch für Graphen mit Millionen von Kanten.
Viele gültige Reihenfolgen
Wenn mehrere Knoten gleichzeitig bereit sind, kann jeder von ihnen als Nächstes verarbeitet werden. Ein DAG besitzt daher oft viele gültige topologische Sortierungen und nicht nur eine.
Schnelltest
Sie beenden Kahns Algorithmus, aber die Reihenfolge enthält weniger als n Knoten. Was bedeutet das?
Rückblick: Kahns Algorithmus
Eingangsgrade zählen, Knoten mit Eingangsgrad null in die Warteschlange einfügen, einen Knoten entnehmen, die Eingangsgrade der Nachbarn verringern und wiederholen. Das ist eine übersichtliche topologische Sortierung in O(V+E). 🚀
Häufig gestellte Fragen
Ist die Lektion „Topologische Sortierung mit Kahns Algorithmus“ kostenlos?
Ja — der vollständige Text von „Topologische Sortierung mit Kahns Algorithmus“ 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 „Topologische Sortierung mit Kahns Algorithmus“?
Ordnen Sie Aufgaben, die voneinander abhängen 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 „Topologische Sortierung mit Kahns Algorithmus“?
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
- Topologische Sortierung mit Kahns Algorithmus
- Zyklen in gerichteten Graphen erkennen
- Stark zusammenhängende Komponenten
- Brücken und Artikulationspunkte