DFS: verbonden componenten en flood fill
Pas DFS toe om verbonden componenten te tellen, los number-of-islands op een 2D-grid op en implementeer flood fill voor beeldverwerking.
DFS: verbonden componenten en flood fill is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 3 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Verbonden componenten gedefinieerd
Een verbonden component in een ongerichte graaf is een maximale verzameling knopen waarvoor tussen elk paar knopen in de verzameling een pad bestaat. Eén graaf kan meerdere niet-verbonden componenten bevatten. Verbonden componenten vinden vormt de basis van veel graafopgaven: groeperen, samenvoegen, eilanden tellen en accounts consolideren zijn allemaal terug te voeren op deze basisbewerking.
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}')Verbonden componenten tellen met DFS
Doorloop alle knopen. Start voor elke onbezette knoop een DFS om alle bereikbare knopen als bezocht te markeren. Elke DFS-start staat voor het ontdekken van één nieuwe component. Tel het aantal DFS-starts om het aantal componenten te bepalen. Dit O(V + E)-algoritme werkt correct ongeacht of de graaf verbonden is.
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)])) # 2Aantal eilanden
Aantal eilanden (LeetCode #200) is het standaardprobleem over verbonden componenten op een 2D-raster. Elke cel met '1' hoort bij een eiland; aangrenzende cellen met '1' (boven/onder/links/rechts) vormen hetzelfde eiland. Tel het aantal afzonderlijke eilanden met DFS: doorloop alle cellen en start wanneer je een nog niet bezochte '1' vindt een DFS die alle verbonden cellen met '1' markeert (vlakvulling); verhoog daarna de teller.
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)) # 3Algoritme voor vlakvulling
Vlakvulling (LeetCode #733) vervangt alle verbonden cellen met een bepaalde beginkleur door een nieuwe kleur — precies zoals het verfemmergereedschap in afbeeldingseditors. Gebruik DFS: begin bij de bronpixel en kleur recursief alle buren opnieuw die dezelfde kleur hebben als de oorspronkelijke kleur. Het belangrijkste randgeval: als de kleur van de startcel al gelijk is aan de nieuwe kleur, retourneer je onmiddellijk om oneindige recursie te voorkomen.
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 eilandoppervlakte
Maximale eilandoppervlakte (LeetCode #695) breidt het tellen van eilanden uit: geef voor elk eiland de grootte van het grootste eiland terug. Tel tijdens de DFS-flood fill de cellen die je markeert. De DFS geeft de grootte van het huidige eiland terug en je houdt het maximum over alle eilanden bij. Dit is een eenvoudige uitbreiding van het patroon voor samenhangende componenten.
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)) # 6Waterstroom naar de Stille en Atlantische Oceaan
Waterstroom naar de Stille en Atlantische Oceaan (LeetCode #417) vraagt welke cellen zowel naar de Stille Oceaan (boven- en linkerrand) als naar de Atlantische Oceaan (onder- en rechterrand) kunnen stromen. Simuleer niet hoe water naar beneden stroomt, maar gebruik omgekeerde DFS: laat het water vanaf de oceanen omhoog stromen. Voer twee DFS-doorlopen uit — één vanaf de randen van de Stille Oceaan en één vanaf de randen van de Atlantische Oceaan — en verzamel de bereikbare cellen. De doorsnede is het antwoord.
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]]))Iteratieve DFS voor samenhangende componenten
Gebruik iteratieve DFS (met een expliciete stapel) om de recursielimiet van Python op grote rasters te vermijden. De iteratieve versie is gelijkwaardig aan recursieve DFS, maar gebruikt een stapel in plaats van de aanroepstapel. Plaats het startknooppunt op de stapel, haal daarna een knooppunt eraf, markeer het als bezocht en plaats niet-bezochte buren op de stapel. Zo kun je rasters met miljoenen cellen veilig verwerken, terwijl recursieve DFS een overloop van de aanroepstapel zou veroorzaken.
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)])) # 3Omgeven gebieden
Omgeven gebieden (LeetCode #130) vindt alle gebieden met 'O' die volledig door randen met 'X' zijn omgeven. Een gebied wordt NIET gevonden als een van de 'O'-cellen de rand van het bord raakt. De truc is om niet rechtstreeks naar omgeven gebieden te zoeken, maar een DFS uit te voeren vanaf alle 'O'-cellen aan de rand en alles wat bereikbaar is als veilig te markeren. Draai daarna de markeringen om: alle overgebleven 'O'-cellen zijn omgeven en worden 'X', terwijl veilige cellen worden teruggezet naar '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, OSubeilanden tellen
Subeilanden tellen (LeetCode #1905) vindt eilanden in grid2 die volledig binnen een eiland in grid1 liggen. Voer DFS uit vanaf elke '1'-cel in grid2: een eiland is een subeiland als elke cel die je bezoekt ook '1' is in grid1. De truc is om ALLE cellen van het eiland te bezoeken (zodat je ze als onderzocht markeert), maar tegelijk bij te houden of ze ALLEMAAL ook '1' waren in grid1. Stop niet meteen bij de eerste '0' in grid1 — dan zou je andere cellen van hetzelfde eiland niet markeren.
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 voor samenhangende componenten
Zowel DFS als BFS vindt alle samenhangende componenten correct, met dezelfde tijdscomplexiteit O(V + E) en ruimtecomplexiteit O(V). DFS is eenvoudiger recursief te implementeren voor problemen met samenhangende componenten, terwijl BFS de voorkeur heeft wanneer je ook informatie over kortste paden nodig hebt. Bij rasterproblemen is DFS cachevriendelijker, omdat het diep in één richting verkent voordat het teruggaat en daarbij opeenvolgende geheugenlocaties in de buurt benadert.
# 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')Eilanden met beperkingen: vormen en omtrekken
Eilandomtrek (LeetCode #463) telt de totale omtrek van het ene eiland in een raster. Tel voor elke landcel ('1') 4 op bij de omtrek en trek daarna 2 af voor elke aangrenzende landcel (gedeelde randen). Voor deze formule-aanpak met O(mn) is geen DFS nodig — maar als je begrijpt dat deze aanpak gelijkwaardig is aan een DFS die randkanten telt, versterkt dat het verband tussen rasterproblemen en redeneren over grafen.
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)) # 16Korte toets
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd hoe je samenhangende componenten vindt met DFS en het bijhouden van bezochte knopen, en hoe je het aantal eilanden en flood fill gebruikt als standaardtoepassingen op tweedimensionale rasters. Ook behandelde je geavanceerde patronen, zoals omgekeerde DFS vanaf randen (omgeven gebieden) en meerdere DFS-doorlopen met het bijhouden van beperkingen (subeilanden). Hierna behandelen we cyclusdetectie in gerichte en ongerichte grafen.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “DFS: verbonden componenten en flood fill” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “DFS: verbonden componenten en flood fill”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “DFS: verbonden componenten en flood fill”?
Pas DFS toe om verbonden componenten te tellen, los number-of-islands op een 2D-grid op en implementeer flood fill voor beeldverwerking. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “DFS: verbonden componenten en flood fill”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Graafrepresentaties en voorbereiding van traversals
- BFS: kortste pad en traversal per niveau
- DFS: verbonden componenten en flood fill
- Cycli detecteren in gerichte en ongerichte grafen