Adjazenzlisten aus der Eingabe
Erstellen Sie den Graphen, den Wettbewerbsaufgaben vorgeben
Adjazenzlisten aus der Eingabe 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 ein Graph wirklich ist
Ein Graph besteht einfach aus Punkten, den sogenannten Knoten, die durch Linien, die sogenannten Kanten, verbunden sind. Durch Straßen verbundene Städte bilden einen Graphen, den Sie bereits kennen. 🗺️
Knoten und Kanten
Jeder Knoten steht für ein Objekt, und jede Kante gibt an, dass zwei Knoten verbunden sind. In Wettbewerbsaufgaben werden Knoten normalerweise von 1 bis n nummeriert.
Die Adjazenzliste
Die bevorzugte Speicherung in Wettbewerbsaufgaben ist eine Adjazenzliste: Für jeden Knoten wird eine Liste seiner direkten Nachbarn geführt.
adj = [[] for _ in range(n + 1)]Warum keine Matrix
Eine Matrix benötigt n² Speicher, was bei großen n schnell zu viel wird. Eine Adjazenzliste speichert nur tatsächlich vorhandene Kanten und lässt sich daher gut skalieren.
Die erste Zeile einlesen
Die meisten Eingaben beginnen mit zwei Zahlen: n Knoten und m Kanten. Lesen Sie diese zuerst ein, damit Sie wissen, wie viele Kanten Sie erwarten.
n, m = map(int, input().split())Eine Kante pro Zeile
Jede der nächsten m Zeilen enthält ein Paar u v. Diese einzelne Kante bedeutet, dass u und v direkt verbunden sind.
u, v = map(int, input().split())Ungerichtet bedeutet beide Richtungen
Bei einer ungerichteten Kante fügen Sie die Verbindung in beide Richtungen hinzu. Sie können von u nach v und von v nach u gehen.
adj[u].append(v)
adj[v].append(u)Gerichtet bedeutet eine Richtung
Bei einer gerichteten Kante speichern Sie nur die Verbindung von u nach v. Lesen Sie die Aufgabenstellung sorgfältig, um zu erkennen, welche Art von Graph vorliegt.
adj[u].append(v)In einer Schleife aufbauen
Führen Sie die Schleife m-mal aus, lesen Sie jedes Paar ein und füllen Sie die Listen. Danach enthält Ihre Adjazenzliste den gesamten Graphen.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)1-basiert vs. 0-basiert
Wenn die Knoten bei 1 beginnen, dimensionieren Sie Ihre Liste mit n + 1, damit der Index n gültig ist. Eine falsche Indizierung verursacht schwer erkennbare Fehler.
Die Nachbarn eines Knotens besuchen
Sobald der Graph aufgebaut ist, wird das Erkunden einfach: Durchlaufen Sie adj eines Knotens, um jeden Nachbarn in einem Schritt zu erreichen.
for nb in adj[u]:
print(nb)Kurztest
Sie lesen eine ungerichtete Kante u v ein. Was speichern Sie?
Rückblick
Sie bauen einen Graphen jetzt als Adjazenzliste auf: Lesen Sie n und m ein, durchlaufen Sie die Kanten und fügen Sie bei ungerichteten Kanten beide Richtungen hinzu. 🎉
Häufig gestellte Fragen
Ist die Lektion „Adjazenzlisten aus der Eingabe“ kostenlos?
Ja — der vollständige Text von „Adjazenzlisten aus der Eingabe“ 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 „Adjazenzlisten aus der Eingabe“?
Erstellen Sie den Graphen, den Wettbewerbsaufgaben vorgeben 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 „Adjazenzlisten aus der Eingabe“?
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
- Adjazenzlisten aus der Eingabe
- BFS für kürzeste ungewichtete Pfade
- DFS, Rekursion und iterative Stapel
- Zusammenhängende Komponenten und Flood Fill