DFS: sammanhängande komponenter och flood fill
Tillämpa DFS för att räkna sammanhängande komponenter, lös number-of-islands i ett 2D-rutnät och implementera flood fill för bildbehandling.
DFS: sammanhängande komponenter och flood fill är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 3 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Definition av sammanhängande komponenter
En sammanhängande komponent i en oriktad graf är en maximal mängd noder sådan att det finns en väg mellan varje par av noder i mängden. En enskild graf kan ha flera osammanhängande komponenter. Att hitta sammanhängande komponenter är grunden för många grafproblem: gruppering, sammanslagning, räkning av öar och konsolidering av konton reduceras alla till denna grundläggande operation.
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}')Räkna sammanhängande komponenter med DFS
Iterera över alla noder. För varje obesökt nod startas en DFS som markerar alla nåbara noder som besökta. Varje DFS-start motsvarar att en ny komponent upptäcks. Räkna antalet DFS-starter för att få antalet komponenter. Denna O(V + E)-algoritm fungerar korrekt oavsett om grafen är sammanhängande eller inte.
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) är det klassiska problemet med sammanhängande komponenter i ett tvådimensionellt rutnät. Varje cell med värdet ’1’ tillhör en ö; intilliggande celler med värdet ’1’ (uppåt/nedåt/vänster/höger) utgör samma ö. Räkna antalet distinkta öar med DFS: iterera över alla celler och starta en DFS när en obesökt ’1’ hittas. Denna DFS markerar alla sammanhängande ’1’-celler (flood fill), varefter räknaren ökas.
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-algoritmen
Flood Fill (LeetCode #733) ersätter alla sammanhängande celler med en given startfärg med en ny färg – precis som färgpytsverktyget i bildredigerare. Använd DFS: börja vid källpixeln och färglägg rekursivt om alla grannar som har originalfärgen. Ett viktigt gränsfall är när startcellens färg redan är samma som den nya färgen; returnera då direkt för att undvika oändlig rekursion.
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]]Största öns area
Största öns area (LeetCode #695) bygger vidare på ö-räkning: för varje ö returnerar ni storleken på den största ön. Under flood fill med DFS räknar ni cellerna som ni markerar. DFS returnerar storleken på den aktuella ön, och ni håller reda på det största värdet bland alla öar. Detta är en enkel utökning av mönstret för sammanhängande komponenter.
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)) # 6Vattenflöde till Stilla havet och Atlanten
Vattenflöde till Stilla havet och Atlanten (LeetCode #417) frågar vilka celler som kan rinna till både Stilla havet (övre/vänstra kanterna) och Atlanten (nedre/högra kanterna). I stället för att simulera vatten som rinner nedåt använder ni omvänd DFS: vatten rinner uppåt från haven. Gör två DFS-sökningar — en från Stilla havets gränser och en från Atlantens gränser — och samla de nåbara cellerna. Snittet är svaret.
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]]))Iterativ DFS för sammanhängande komponenter
Använd iterativ DFS (med en explicit stack) för att undvika Pythons rekursionsgräns på stora gitter. Den iterativa versionen motsvarar rekursiv DFS men använder en stack i stället för anropsstacken. Lägg startnoden på stacken, ta sedan bort en nod, markera den som besökt och lägg obesökta grannar på stacken. Detta hanterar gitter med upp till miljontals celler säkert, där rekursiv DFS annars skulle orsaka stackoverflow.
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)])) # 3Omringade regioner
Omringade regioner (LeetCode #130) hittar alla regioner med 'O' som är helt omgivna av kanter med 'X'. En region fångas INTE om någon av dess 'O'-celler vidrör spelplanens kant. Tricket är att i stället för att hitta omringade regioner direkt göra en DFS från alla 'O'-celler på kanten och markera allt som kan nås som säkert. Vänd sedan: alla återstående 'O'-celler är omringade och blir 'X', medan säkra celler återställs till 'O'.
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, ORäkna delöar
Räkna delöar (LeetCode #1905) hittar öar i grid2 som helt ryms inom en ö i grid1. Gör DFS från varje cell med '1' i grid2: en ö är en delö om varje cell som den besöker också är '1' i grid1. Tricket är att besöka ALLA celler på ön (så att de markeras som utforskade), men samtidigt hålla reda på om ALLA också var '1' i grid1. Avbryt inte vid det första '0' i grid1 — då missar ni att markera andra celler på samma ö.
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 kontra BFS för sammanhängande komponenter
Både DFS och BFS hittar korrekt alla sammanhängande komponenter med samma tidskomplexitet O(V + E) och minneskomplexitet O(V). DFS är enklare att implementera rekursivt för problem med sammanhängande komponenter, medan BFS föredras när ni också behöver information om kortaste vägar. I gitterproblem är DFS mer cachevänlig eftersom den utforskar på djupet i en riktning innan den backar tillbaka och därmed läser närliggande minnespositioner sekventiellt.
# 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')Öar med begränsningar: former och omkretsar
Öns omkrets (LeetCode #463) räknar den totala omkretsen för den enda ön i ett gitter. För varje landcell ('1') lägger ni till 4 till omkretsen och subtraherar sedan 2 för varje intilliggande landcell (delade kanter). Denna O(mn)-metod baserad på en formel kräver ingen DFS — men förståelsen av att den motsvarar en DFS som räknar gränskanter förstärker kopplingen mellan gitterproblem och grafresonemang.
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)) # 16Snabbtest
Testa era kunskaper i begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen lärde ni er: sammanhängande komponenter via DFS med besöksmarkering, antal öar och flood fill som klassiska tillämpningar av 2D-gitter, samt avancerade mönster som omvänd DFS från gränser (omringade regioner) och flera DFS-sökningar med villkorskontroll (delöar). Härnäst tar vi oss an cykeldetektering i riktade och oriktade grafer.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”DFS: sammanhängande komponenter och flood fill” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”DFS: sammanhängande komponenter och flood fill”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”DFS: sammanhängande komponenter och flood fill”?
Tillämpa DFS för att räkna sammanhängande komponenter, lös number-of-islands i ett 2D-rutnät och implementera flood fill för bildbehandling. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”DFS: sammanhängande komponenter och flood fill”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Grafrepresentationer och förberedelser för genomgång
- BFS: kortaste väg och nivågenomgång
- DFS: sammanhängande komponenter och flood fill
- Cykeldetektering i riktade och oriktade grafer