0Pricing
DSA Interview Prep · Lektion

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 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.

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)]))          # 2

Number 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))  # 3

Flood-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))  # 6

Wasserfluss 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)]))  # 3

Umgebene 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, O

Teilinseln 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]]))  # 1

DFS 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))  # 16

Kurzer 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 DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA 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 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 „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 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

  1. Graphdarstellungen und Vorbereitung der Traversierung
  2. BFS: kürzester Pfad und Ebenendurchlauf
  3. DFS: Zusammenhangskomponenten und Flood Fill
  4. Zykluserkennung in gerichteten und ungerichteten Graphen
← Zurück zu DSA Interview Prep