Course Schedule I und II
Modellieren Sie Kursvoraussetzungen als gerichteten Graphen und verwenden Sie topologische Sortierung, um zu bestimmen, ob alle Kurse absolviert werden können und in welcher Reihenfolge.
Course Schedule I und II ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Problemübersicht
Course Schedule I (LeetCode 207): Gegeben sind n Kurse und eine Liste von prerequisites-Paaren [a, b], wobei „b muss vor a belegt werden“ bedeutet. Bestimmen Sie, ob Sie alle Kurse abschließen können. Course Schedule II (LeetCode 210): Geben Sie die tatsächliche Reihenfolge zurück, in der die Kurse belegt werden müssen, oder ein leeres Array, wenn dies nicht möglich ist. Beide Aufgaben lassen sich auf eine topologische Sortierung eines gerichteten Graphen reduzieren, in dem die Voraussetzungen durch Kanten dargestellt werden.
Modellierung des Graphen
Erstellen Sie einen gerichteten Graphen: Fügen Sie für jedes Voraussetzungenpaar [a, b] die Kante b → a hinzu („b muss vor a kommen“ bedeutet, dass b zu a führt). Berechnen Sie die Eingangsgrade für jeden Kurs. Ein Kurs mit Eingangsgrad 0 hat keine Voraussetzungen und kann sofort belegt werden. Die Aufgabe ist genau dann lösbar, wenn in diesem Graphen kein Zyklus existiert (also keine zirkuläre Abhängigkeit).
from collections import defaultdict
def build_graph(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for a, b in prerequisites: # b must come before a
graph[b].append(a)
in_degree[a] += 1
return graph, in_degree
graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind) # [0, 1, 1, 2]
print('Graph edges:', dict(graph))Course Schedule I: Lösung mit Kahn
Verwenden Sie Kahns Algorithmus. Wenn die Anzahl der verarbeiteten Kurse n entspricht, können alle Kurse abgeschlossen werden. Andernfalls verhindert eine zirkuläre Abhängigkeit den Abschluss.
from collections import deque, defaultdict
def canFinish(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)
count = 0
while queue:
course = queue.popleft()
count += 1
for nxt in graph[course]:
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]])) # FalseCourse Schedule II: Reihenfolge zurückgeben
Wie bei Course Schedule I, aber sammeln Sie zusätzlich die Reihenfolge der Kurse, während Sie sie verarbeiten. Geben Sie die Reihenfolge zurück, wenn alle Kurse enthalten sind, andernfalls eine leere Liste.
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:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
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]]))Course Schedule mit DFS
Eine Alternative ist die Zykluserkennung mit DFS. Kurse haben drei Zustände: unbesucht (0), in Bearbeitung (1), abgeschlossen (2). Wenn Sie während der DFS einen Kurs erreichen, der gerade bearbeitet wird, existiert ein Zyklus. Dieser Ansatz ist funktional gleichwertig zu Kahn, verwendet jedoch eine rekursive DFS.
from collections import defaultdict
def canFinish_dfs(numCourses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
# 0=unvisited, 1=in-progress, 2=done
state = [0] * numCourses
def has_cycle(course):
if state[course] == 1: return True # back edge
if state[course] == 2: return False # already cleared
state[course] = 1
for nxt in graph[course]:
if has_cycle(nxt):
return True
state[course] = 2
return False
return not any(has_cycle(i) for i in range(numCourses))
print(canFinish_dfs(2, [[1,0]])) # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # FalseWarum die Richtung der Kanten wichtig ist
Ein häufiger Fehler besteht darin, die Richtung der Kanten umzukehren: Wenn [a, b] bedeutet, dass „b vor a“ kommt, fügen Sie die Kante b → a hinzu, nicht a → b. Die Richtung der Kante muss den Abhängigkeitsfluss widerspiegeln: Ein Pfeil zeigt von dem, was zuerst erledigt werden muss, zu dem, was davon abhängt. Bei der falschen Richtung werden Zykluserkennung und Reihenfolge umgekehrt, was bei Aufgaben mit mehreren Abhängigkeiten zu falschen Ergebnissen führt.
Course Schedule III: Greedy-Variante
Course Schedule III (LeetCode 630) ist ein anderes Problem: Kurse haben Bearbeitungszeiten und Fristen, und Sie möchten die größtmögliche Anzahl an Kursen belegen. Dieses Problem wird greedy mit einem Max-Heap gelöst: Belegen Sie immer zuerst den Kurs mit der spätesten Frist. Wenn das Hinzufügen eines Kurses seine Frist überschreitet, ersetzen Sie ihn durch den längsten bisher belegten Kurs (falls dieser länger ist). Dies ist ein Greedy- und kein Problem der topologischen Sortierung — das zeigt, wie wichtig es ist, Aufgabenstellungen sorgfältig zu lesen.
Umgang mit isolierten Knoten
Kurse ohne Voraussetzungen und ohne abhängige Kurse sind isolierte Knoten — sie haben den Eingangsgrad 0 und keine ausgehenden Kanten. Kahns Algorithmus verarbeitet sie korrekt: Sie werden sofort in die Queue eingereiht und verarbeitet. Achten Sie darauf, die Eingangsgrade für ALLE Knoten von 0 bis n-1 mit 0 zu initialisieren, auch für Knoten, die nicht in der Liste der Voraussetzungen vorkommen, da sie sonst übersehen werden.
# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict
def findOrder_isolated(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses # initialise ALL nodes
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:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder_isolated(4, [[1,0]])) # [0,1,2,3] or [2,3,0,1] etc.Zeit für den parallelen Abschluss von Kursen
Parallel Courses II: Bestimmen Sie die minimale Anzahl an Semestern, die benötigt wird, um alle Kurse abzuschließen, wenn pro Semester höchstens k Kurse belegt werden dürfen und die Voraussetzungen eingehalten werden müssen. Dies erfordert eine Verarbeitung von Kahn auf Ebenen kombiniert mit Bitmasken-DP für die Auswahlbeschränkung durch k — ein deutlich schwierigeres Problem, das topologische Sortierung mit Bitmasken-DP verbindet.
Strategie für die Kommunikation im Vorstellungsgespräch
Wenn Sie in einem Vorstellungsgespräch mit einer Aufgabe vom Typ Course Schedule konfrontiert werden: (1) Erkennen Sie sofort, dass es sich um ein Problem der topologischen Sortierung bzw. Zykluserkennung handelt. (2) Modellieren Sie den Graphen, indem Sie klären, in welche Richtung die Kanten zeigen. (3) Wählen Sie Kahn (BFS) wegen seiner Einfachheit oder DFS, wenn Sie damit vertrauter sind. (4) Behandeln Sie den Fall eines Zyklus ausdrücklich. (5) Nennen Sie die Zeitkomplexität O(V+E). Dieser strukturierte Ansatz zeigt systematische Fähigkeiten zur Problemlösung.
Umfassender Test
Testen Sie beide Lösungen mit einer Reihe von Eingaben, um ihre Korrektheit zu überprüfen. Der Ansatz von Kahn kommt problemlos mit mehreren gültigen Reihenfolgen zurecht — für Course Schedule II ist jede gültige topologische Reihenfolge als Antwort zulässig.
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:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(1, [])) # [0]
print(findOrder(2, [[0,1]])) # [1, 0]
print(findOrder(3, [[1,0],[2,1]])) # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]])) # [] cycleKurze Überprüfung
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Course Schedule I und II verwenden beide eine topologische Sortierung mit der Kante b → a für die Voraussetzung [a, b], Course Schedule I prüft lediglich len(order) == n, während Course Schedule II die Reihenfolge selbst zurückgibt und die DFS-basierte Zykluserkennung mit drei Zuständen eine gültige Alternative zu Kahns BFS-Ansatz ist. Als Nächstes untersuchen wir Kosarajus Algorithmus für stark zusammenhängende Komponenten.
Häufig gestellte Fragen
Ist die Lektion „Course Schedule I und II“ kostenlos?
Ja — der vollständige Text von „Course Schedule I und II“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Course Schedule I und II“?
Modellieren Sie Kursvoraussetzungen als gerichteten Graphen und verwenden Sie topologische Sortierung, um zu bestimmen, ob alle Kurse absolviert werden können und in welcher Reihenfolge. Du übst DSA 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 DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA 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 3 von 4.
Wie lange dauert die Lektion „Course Schedule I und II“?
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 DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA 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