DFS: sammenhengende komponenter og flood fill
Bruk DFS til å telle sammenhengende komponenter, løs number-of-islands i et 2D-rutenett og implementer flood fill for bildebehandling.
DFS: sammenhengende komponenter og flood fill er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Definisjon av sammenhengende komponenter
En sammenhengende komponent i en urettet graf er en maksimal mengde noder der det finnes en vei mellom hvert nodepar i mengden. Én graf kan ha flere usammenhengende komponenter. Å finne sammenhengende komponenter er grunnlaget for mange grafoppgaver: gruppering, sammenslåing, telling av øyer og konsolidering av kontoer kan alle reduseres til denne grunnleggende operasjonen.
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}')Telling av sammenhengende komponenter med DFS
Gå gjennom alle noder. For hver ubesøkte node startes et DFS-søk for å merke alle nåbare noder som besøkt. Hver oppstart av et DFS-søk tilsvarer oppdagelsen av én ny komponent. Tell antallet DFS-søk for å finne antallet komponenter. Denne algoritmen med O(V + E) fungerer korrekt enten grafen er sammenhengende eller ikke.
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) er det klassiske problemet med sammenhengende komponenter på et todimensjonalt rutenett. Hver celle med '1' tilhører en øy, og tilstøtende celler med '1' (opp/ned/venstre/høyre) utgjør den samme øya. Tell antallet ulike øyer med DFS: gå gjennom alle cellene, og start et DFS-søk når en ubesøkt '1' blir funnet. Søkningen merker alle sammenhengende celler med '1' (flomfylling), og deretter økes antallet.
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)) # 3Flomfyllingsalgoritmen
Flood Fill (LeetCode #733) erstatter alle sammenhengende celler med en gitt startfarge med en ny farge – akkurat som malingsbøtteverktøyet i bilderedigeringsprogrammer. Bruk DFS: start ved kildepikselet, og fargelegg rekursivt alle naboer som har den opprinnelige fargen. Det viktige spesialtilfellet er at dersom startcellens farge allerede er lik den nye fargen, må funksjonen returnere umiddelbart for å unngå uendelig rekursjon.
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ørste øyareal
Største øyareal (LeetCode #695) utvider telling av øyer: For hver øy finner du størrelsen på den største. Under DFS-flomfyllingen teller du cellene du markerer. DFS returnerer størrelsen på den gjeldende øya, og du holder oversikt over maksimumet blant alle øyene. Dette er en enkel utvidelse av mønsteret for sammenhengende 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)) # 6Vannflyt til Stillehavet og Atlanterhavet
Vannflyt til Stillehavet og Atlanterhavet (LeetCode #417) spør hvilke celler vann kan renne fra til både Stillehavet (øverste og venstre kant) og Atlanterhavet (nederste og høyre kant). I stedet for å simulere vann som renner nedover, bruker du omvendt DFS: Vannet flyter oppover fra havene. Gjør to DFS-gjennomganger – én fra Stillehavets kanter og én fra Atlanterhavets kanter – og samle cellene som kan nås. Snittet er 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 for sammenhengende komponenter
Bruk iterativ DFS (med en eksplisitt stakk) for å unngå Pythons rekursjonsgrense på store rutenett. Den iterative versjonen er ekvivalent med rekursiv DFS, men bruker en stakk i stedet for kallstakken. Legg startnoden på stakken, ta deretter ut en node, marker den som besøkt og legg ubesøkte naboer på stakken. Dette håndterer rutenett med opptil millioner av celler på en trygg måte, mens rekursiv DFS ville ha ført til stakkoverflyt.
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)])) # 3Omringede regioner
Omringede regioner (LeetCode #130) finner alle «O»-regioner som er fullstendig omgitt av «X»-kanter. En region blir IKKE fanget opp hvis noen av «O»-cellene berører kanten av brettet. Trikset er å gjøre DFS fra alle «O»-celler på kanten og markere alt som kan nås, som trygt. Snu deretter: Alle gjenværende «O»-celler er omringet og blir til «X», mens trygge celler gjenopprettes til «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, OTell deløyer
Tell deløyer (LeetCode #1905) finner øyer i grid2 som er fullstendig inkludert i en øy i grid1. Start DFS fra hver celle med «1» i grid2: En øy er en deløy hvis hver celle den besøker, også er «1» i grid1. Trikset er å besøke ALLE cellene på øya (slik at de markeres som utforsket), men samtidig holde oversikt over om ALLE også var «1» i grid1. Ikke avslutt ved den første «0»-en i grid1 – da ville du ikke ha markert de andre cellene på samme øy.
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 versus BFS for sammenhengende komponenter
Både DFS og BFS finner alle sammenhengende komponenter korrekt, med samme tidskompleksitet på O(V + E) og plasskompleksitet på O(V). DFS er enklere å implementere rekursivt for problemer med sammenhengende komponenter, mens BFS foretrekkes når du også trenger informasjon om korteste vei. I rutenettproblemer er DFS mer cache-vennlig fordi den utforsker dypt i én retning før den går tilbake, og dermed får tilgang til nærliggende minneområder sekvensielt.
# 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')Øyer med begrensninger: former og omkretser
Øyomkrets (LeetCode #463) teller den totale omkretsen til den ene øya i et rutenett. For hver landcelle («1») legger du 4 til omkretsen, og trekker deretter fra 2 for hver tilstøtende landcelle (felles kanter). Denne formelbaserte O(mn)-tilnærmingen krever ingen DFS – men forståelsen av at den tilsvarer en DFS som teller grensekanter, forsterker sammenhengen mellom rutenettproblemer og grafresonnering.
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)) # 16Hurtigsjekk
Test forståelsen din av konsepter fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du: sammenhengende komponenter med DFS og sporing av besøkte noder, antall øyer og flomfylling som kanoniske bruksområder for todimensjonale rutenett, samt avanserte mønstre som omvendt DFS fra kanter (omringede regioner) og flere DFS-gjennomganger med sporing av begrensninger (deløyer). Neste tema er syklusdeteksjon i rettede og urettede grafer.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «DFS: sammenhengende komponenter og flood fill» gratis?
Ja – hele teksten i «DFS: sammenhengende komponenter og flood fill» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «DFS: sammenhengende komponenter og flood fill»?
Bruk DFS til å telle sammenhengende komponenter, løs number-of-islands i et 2D-rutenett og implementer flood fill for bildebehandling. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «DFS: sammenhengende komponenter og flood fill»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Grafrepresentasjoner og oppsett for traversering
- BFS: korteste sti og nivågjennomgang
- DFS: sammenhengende komponenter og flood fill
- Syklusdeteksjon i rettede og urettede grafer