Zusammenhängende Komponenten und Flood Fill
Zählen Sie Inseln und kennzeichnen Sie Regionen
Zusammenhängende Komponenten und Flood Fill ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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 Komponente ist
Eine zusammenhängende Komponente ist eine Gruppe von Knoten, in der jeder Knoten von jedem anderen aus erreichbar ist. Ein Graph kann mehrere voneinander getrennte Gruppen enthalten. 🧩
Komponenten zählen
Um Komponenten zu zählen, führen Sie von jedem unbesuchten Knoten eine Traversierung aus. Jeder neue Startpunkt markiert eine vollständig neue Gruppe.
Alle Knoten durchlaufen
Durchlaufen Sie die Knoten von 1 bis n. Wenn Sie einen noch unbesuchten Knoten finden, haben Sie eine neue Komponente entdeckt, die erkundet werden muss.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Eine Traversierung pro Gruppe
Die innere BFS oder DFS markiert die gesamte Komponente als besucht, sodass die äußere Schleife sie beim nächsten Durchlauf überspringt.
Auch Gitter sind Graphen
Ein zweidimensionales Gitter ist ein versteckter Graph: Jede Zelle ist ein Knoten, der mit seinen Nachbarn verbunden ist. Dadurch wird die klassische Idee des flood fill möglich. 🗺️
Die vier Richtungen
Von einer Zelle aus bewegen Sie sich normalerweise nach oben, unten, links oder rechts. Speichern Sie diese Bewegungen als Richtungsvektoren, damit der Code übersichtlich bleibt.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Innerhalb des Gitters bleiben
Prüfen Sie vor jedem Schritt, ob sich die neue Zeile und Spalte innerhalb des Gültigkeitsbereichs befinden. Wenn Sie diese Prüfung überspringen, führt das zu Indexfehlern oder falschen Ergebnissen.
if 0 <= nr < rows and 0 <= nc < cols:
passEine Region per Flood Fill füllen
Flood Fill startet in einer Zelle und breitet sich auf jede verbundene Zelle desselben Typs aus – genau wie das Farbeimer-Werkzeug.
Inseln zählen
Um Inseln zu zählen, durchlaufen Sie das Gitter. Bei jeder neuen Landzelle füllen Sie die gesamte zugehörige Insel per Flood Fill und erhöhen den Zähler um eins.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Regionen beschriften
Sie können während des Füllens pro Zelle ein Label speichern. Später wissen Sie dadurch sofort, zu welcher Region eine Zelle gehört.
Linear zur Gittergröße
Jede Zelle wird einmal besucht. Daher läuft Flood Fill auf einem Gitter in O(rows mal cols). Das liegt problemlos innerhalb der Zeitlimits von Programmierwettbewerben.
Schnelltest
Wie zählen Sie zusammenhängende Komponenten?
Zusammenfassung
Sie zählen Komponenten, indem Sie von jedem noch nicht besuchten Knoten aus eine Traversierung starten. Auf Gittern verwenden Sie Flood Fill, um Regionen zu beschriften und Inseln zu zählen. 🎉
Häufig gestellte Fragen
Ist die Lektion „Zusammenhängende Komponenten und Flood Fill“ kostenlos?
Ja — der vollständige Text von „Zusammenhängende Komponenten und Flood Fill“ 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 „Zusammenhängende Komponenten und Flood Fill“?
Zählen Sie Inseln und kennzeichnen Sie Regionen 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 4 von 4.
Wie lange dauert die Lektion „Zusammenhängende Komponenten und Flood Fill“?
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