DFS: Zusammenhangskomponenten und Flood Fill
Wenden Sie DFS an, um Zusammenhangskomponenten zu zählen, number-of-islands in einem 2D-Raster zu lösen und Flood Fill für die Bildverarbeitung zu implementieren.
DFS: Zusammenhangskomponenten und Flood Fill ist eine kostenlose Coding 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Zusammenhängende Komponenten definiert
Eine zusammenhängende Komponente in einem ungerichteten Graphen ist eine maximale Menge von Knoten, sodass zwischen jedem Knotenpaar in dieser Menge ein Weg existiert. Ein einzelner Graph kann mehrere nicht zusammenhängende Komponenten enthalten. Das Finden zusammenhängender Komponenten bildet die Grundlage vieler Graphaufgaben: Gruppieren, Zusammenführen, Inselzählung und Kontenzusammenführung lassen sich alle auf dieses Grundmuster zurückführen.
from collections import defaultdict
# Graph with 3 components: {0,1,2}, {3,4}, {5}
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,2),(3,4)]:
graph[u].append(v)
graph[v].append(u)
# Node 5 is isolated (no edges)
for node in [0,1,2,3,4,5]:
if node not in graph:
graph[node] = []
# We need DFS or BFS from each unvisited node
# to discover all components
print('Graph has nodes 0-5 with components: {0,1,2}, {3,4}, {5}')Zusammenhängende Komponenten mit DFS zählen
Durchlaufen Sie alle Knoten. Starten Sie für jeden unbesuchten Knoten eine DFS, die alle erreichbaren Knoten als besucht markiert. Jeder DFS-Start entspricht dem Entdecken einer neuen Komponente. Zählen Sie die DFS-Starts, um die Anzahl der Komponenten zu ermitteln. Dieser Algorithmus mit O(V + E) funktioniert unabhängig davon, ob der Graph zusammenhängend ist oder nicht.
from collections import defaultdict
def count_components(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)
for node in range(n):
if node not in visited:
dfs(node)
count += 1
return count
print(count_components(6, [(0,1),(0,2),(1,2),(3,4)])) # 3
print(count_components(5, [(0,1),(1,2),(3,4)])) # 2Number of Islands
Number of Islands (LeetCode #200) ist das kanonische Problem zu zusammenhängenden Komponenten in einem 2D-Gitter. Jede „1“-Zelle gehört zu einer Insel; benachbarte „1“-Zellen (oben/unten/links/rechts) bilden dieselbe Insel. Ermitteln Sie die Anzahl der unterschiedlichen Inseln mit DFS: Durchlaufen Sie alle Zellen und starten Sie bei einer unbesuchten „1“ eine DFS, die alle verbundenen „1“-Zellen markiert (Flood Fill). Erhöhen Sie anschließend den Zähler.
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '#' # mark visited in-place
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
grid = [['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']]
print(num_islands(grid)) # 3Flood-Fill-Algorithmus
Flood Fill (LeetCode #733) ersetzt alle zusammenhängenden Zellen einer bestimmten Ausgangsfarbe durch eine neue Farbe – genau wie das Farbeimerwerkzeug in Bildbearbeitungsprogrammen. Verwenden Sie DFS: Beginnen Sie beim Quellpixel und färben Sie rekursiv alle Nachbarn neu, die der ursprünglichen Farbe entsprechen. Der entscheidende Sonderfall: Wenn die Farbe der Ausgangszelle bereits der neuen Farbe entspricht, kehren Sie sofort zurück, um unendliche Rekursion zu vermeiden.
def flood_fill(image, sr, sc, new_color):
original = image[sr][sc]
if original == new_color:
return image # edge case: same color, nothing to do
rows, cols = len(image), len(image[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = new_color
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
dfs(sr, sc)
return image
image = [[1,1,1],[1,1,0],[1,0,1]]
result = flood_fill(image, 1, 1, 2)
for row in result: print(row)
# [[2,2,2],[2,2,0],[2,0,1]]Maximale Inselfläche
Maximale Inselfläche (LeetCode #695) erweitert das Zählen von Inseln: Für jede Insel soll die Größe der größten Insel zurückgegeben werden. Zählen Sie während des DFS-Flood-Fills die markierten Zellen. Die DFS gibt die Größe der aktuellen Insel zurück, und Sie verfolgen das Maximum über alle Inseln hinweg. Dies ist eine einfache Erweiterung des Musters für zusammenhängende Komponenten.
def max_area_of_island(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
if grid[r][c] != 1:
return 0
grid[r][c] = 0 # mark visited
return (1 + dfs(r+1,c) + dfs(r-1,c) +
dfs(r,c+1) + dfs(r,c-1))
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
max_area = max(max_area, dfs(r, c))
return max_area
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0]]
print(max_area_of_island(grid)) # 6Wasserfluss zum Pazifik und Atlantik
Wasserfluss zum Pazifik und Atlantik (LeetCode #417) fragt, welche Zellen sowohl zum Pazifik (oberer und linker Rand) als auch zum Atlantik (unterer und rechter Rand) abfließen können. Anstatt die Abwärtsbewegung des Wassers zu simulieren, verwenden Sie eine umgekehrte DFS: Das Wasser fließt von den Ozeanen aus nach oben. Führen Sie zwei DFS-Durchläufe aus – einen von den Rändern des Pazifiks und einen von den Rändern des Atlantiks – und sammeln Sie die erreichbaren Zellen. Der Schnitt dieser Mengen ist die Lösung.
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
pac = set(); atl = set()
def dfs(r, c, visited, prev_h):
if (r,c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
return
if heights[r][c] < prev_h:
return # water can't flow uphill in reverse
visited.add((r,c))
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc, visited, heights[r][c])
for r in range(rows):
dfs(r, 0, pac, heights[r][0]) # Pacific left
dfs(r, cols-1, atl, heights[r][cols-1]) # Atlantic right
for c in range(cols):
dfs(0, c, pac, heights[0][c]) # Pacific top
dfs(rows-1, c, atl, heights[rows-1][c]) # Atlantic bottom
return sorted(pac & atl) # intersection
print(pacific_atlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))Iterative DFS für zusammenhängende Komponenten
Verwenden Sie eine iterative DFS (mit einem expliziten Stack), um bei großen Gittern das Rekursionslimit von Python zu vermeiden. Die iterative Variante ist äquivalent zur rekursiven DFS, verwendet aber einen Stack statt des Aufruf-Stacks. Legen Sie den Startknoten auf den Stack, entfernen Sie anschließend jeweils einen Knoten, markieren Sie ihn als besucht und legen Sie unbesuchte Nachbarn auf den Stack. So lassen sich Gitter mit bis zu Millionen von Zellen sicher verarbeiten, während eine rekursive DFS einen Stacküberlauf verursachen würde.
def count_components_iterative(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
for start in range(n):
if start in visited:
continue
# Iterative DFS
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for nb in graph[node]:
if nb not in visited:
stack.append(nb)
count += 1
return count
print(count_components_iterative(6, [(0,1),(0,2),(1,2),(3,4)])) # 3Umgebene Regionen
Umgebene Regionen (LeetCode #130) erfasst alle 'O'-Regionen, die vollständig von 'X'-Rändern umgeben sind. Eine Region wird NICHT erfasst, wenn eine ihrer 'O'-Zellen den Rand des Spielfelds berührt. Der entscheidende Trick: Suchen Sie umgebene Regionen nicht direkt, sondern führen Sie von allen 'O'-Zellen am Rand eine DFS durch und markieren Sie alles Erreichbare als sicher. Anschließend kehren Sie die Markierungen um: Alle verbleibenden 'O'-Zellen sind umgeben und werden zu 'X', während sichere Zellen wieder zu 'O' werden.
def solve(board):
if not board:
return
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if board[r][c] != 'O':
return
board[r][c] = 'S' # safe: connected to border
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
# Mark border-connected O's as safe
for r in range(rows):
dfs(r, 0); dfs(r, cols-1)
for c in range(cols):
dfs(0, c); dfs(rows-1, c)
# Flip: surrounded O -> X, safe S -> O
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O': board[r][c] = 'X'
elif board[r][c] == 'S': board[r][c] = 'O'
board = [['X','X','X','X'],['X','O','O','X'],
['X','X','O','X'],['X','O','X','X']]
solve(board)
print([board[1][1], board[3][1]]) # X, OTeilinseln zählen
Teilinseln zählen (LeetCode #1905) findet Inseln in grid2, die vollständig innerhalb einer Insel in grid1 liegen. Starten Sie von jeder '1'-Zelle in grid2 eine DFS: Eine Insel ist eine Teilinsel, wenn jede von ihr besuchte Zelle in grid1 ebenfalls '1' ist. Der entscheidende Trick: Besuchen Sie ALLE Zellen der Insel, um sie als untersucht zu markieren, und verfolgen Sie gleichzeitig, ob sie ALLE auch in grid1 '1' waren. Brechen Sie nicht beim ersten '0' in grid1 ab – sonst würden Sie die übrigen Zellen derselben Insel nicht markieren.
def count_sub_islands(grid1, grid2):
rows, cols = len(grid2), len(grid2[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return True
if grid2[r][c] != 1:
return True
grid2[r][c] = 0 # mark visited
is_sub = grid1[r][c] == 1 # this cell must be in grid1
is_sub = dfs(r+1,c) and is_sub # note: AND not short-circuit OR
is_sub = dfs(r-1,c) and is_sub
is_sub = dfs(r,c+1) and is_sub
is_sub = dfs(r,c-1) and is_sub
return is_sub
count = 0
for r in range(rows):
for c in range(cols):
if grid2[r][c] == 1 and dfs(r, c):
count += 1
return count
print(count_sub_islands([[1,1,1],[1,0,1],[1,1,1]],
[[1,1,1],[1,0,1],[1,1,1]])) # 1DFS vs. BFS für zusammenhängende Komponenten
Sowohl DFS als auch BFS finden alle zusammenhängenden Komponenten korrekt und haben dieselbe Zeitkomplexität von O(V + E) sowie dieselbe Speicherkomplexität von O(V). Für Probleme mit zusammenhängenden Komponenten ist eine rekursive DFS einfacher zu implementieren, während BFS bevorzugt wird, wenn Sie zusätzlich Informationen über kürzeste Pfade benötigen. Bei Gitterproblemen ist DFS cache-freundlicher, da sie zunächst tief in eine Richtung sucht, bevor sie zurückgeht, und dabei auf aufeinanderfolgende Speicherbereiche in der Nähe zugreift.
# DFS advantages for connected components:
# - Simpler recursive implementation
# - Lower constant factor for small graphs
# - Can restore grid state during backtracking (if needed)
# BFS advantages:
# - Finds shortest path while traversing
# - Better for wide, shallow graphs (avoids deep recursion)
# - Multi-source initialisation is natural
# Same asymptotic complexity: O(V + E) time, O(V) space
# Grid (m rows, n cols): O(mn) time and space
print('DFS and BFS: same O(V+E) complexity for component counting')Inseln mit Einschränkungen: Formen und Umfänge
Inselumfang (LeetCode #463) zählt den gesamten Umfang der einzigen Insel in einem Gitter. Addieren Sie für jede Landzelle ('1') 4 zum Umfang und ziehen Sie anschließend für jede angrenzende Landzelle 2 ab (gemeinsame Kanten). Dieser formelbasierte Ansatz mit O(mn) benötigt keine DFS – das Verständnis, dass er einer DFS entspricht, die Randkanten zählt, verdeutlicht jedoch die Verbindung zwischen Gitterproblemen und dem Denken in Graphen.
def island_perimeter(grid):
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += 4 # start with 4 sides
# Subtract shared edges with adjacent land cells
if r > 0 and grid[r-1][c] == 1:
perimeter -= 2 # shared top edge
if c > 0 and grid[r][c-1] == 1:
perimeter -= 2 # shared left edge
return perimeter
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(island_perimeter(grid)) # 16Kurzer Test
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 Folgendes gelernt: zusammenhängende Komponenten mit DFS und Besuchsmarkierungen, Anzahl der Inseln und Flood Fill als grundlegende Anwendungen auf 2D-Gittern sowie fortgeschrittene Muster wie umgekehrte DFS von den Rändern aus (umgebene Regionen) und mehrfache DFS mit Verfolgung von Einschränkungen (Teilinseln). Als Nächstes beschäftigen wir uns mit der Zykluserkennung in gerichteten und ungerichteten Graphen.
Häufig gestellte Fragen
Ist die Lektion „DFS: Zusammenhangskomponenten und Flood Fill“ kostenlos?
Ja — der vollständige Text von „DFS: Zusammenhangskomponenten 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 „DFS: Zusammenhangskomponenten und Flood Fill“?
Wenden Sie DFS an, um Zusammenhangskomponenten zu zählen, number-of-islands in einem 2D-Raster zu lösen und Flood Fill für die Bildverarbeitung zu implementieren. 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 3 von 4.
Wie lange dauert die Lektion „DFS: Zusammenhangskomponenten 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
- Graphdarstellungen und Vorbereitung der Traversierung
- BFS: kürzester Pfad und Ebenendurchlauf
- DFS: Zusammenhangskomponenten und Flood Fill
- Zykluserkennung in gerichteten und ungerichteten Graphen