DFS: spójne składowe i flood fill
Zastosują Państwo DFS do zliczania spójnych składowych, rozwiążą zadanie number-of-islands na siatce 2D i zaimplementują flood fill do przetwarzania obrazów.
DFS: spójne składowe i flood fill to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Definicja składowych spójnych
Składowa spójna w grafie nieskierowanym to maksymalny zbiór wierzchołków, taki że między każdą parą wierzchołków w tym zbiorze istnieje ścieżka. Jeden graf może zawierać wiele niespójnych składowych. Znajdowanie składowych spójnych stanowi podstawę wielu problemów grafowych: grupowanie, scalanie, liczenie wysp i konsolidacja kont sprowadzają się do tej operacji.
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}')Liczenie składowych spójnych za pomocą DFS
Należy przejść po wszystkich wierzchołkach. Dla każdego nieodwiedzonego wierzchołka należy uruchomić DFS, aby oznaczyć jako odwiedzone wszystkie osiągalne wierzchołki. Każde uruchomienie DFS odpowiada znalezieniu jednej nowej składowej. Liczba uruchomień DFS jest więc liczbą składowych. Ten algorytm o złożoności O(V + E) działa poprawnie niezależnie od tego, czy graf jest spójny.
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) to klasyczny problem składowych spójnych na siatce 2D. Każda komórka „1” należy do wyspy, a sąsiadujące komórki „1” (w górę, w dół, w lewo i w prawo) tworzą tę samą wyspę. Liczbę odrębnych wysp należy policzyć za pomocą DFS: przejść po wszystkich komórkach, a po znalezieniu nieodwiedzonej komórki „1” uruchomić DFS, który oznaczy wszystkie połączone komórki „1” (wypełnianie obszaru), a następnie zwiększyć licznik.
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)) # 3Algorytm Flood Fill
Flood Fill (LeetCode #733) zastępuje wszystkie połączone komórki o danym kolorze początkowym nowym kolorem — dokładnie tak jak narzędzie wiadra z farbą w edytorach obrazów. Należy użyć DFS: rozpocząć od piksela źródłowego i rekurencyjnie zmienić kolor wszystkich sąsiadów, którzy mają pierwotny kolor. Kluczowy przypadek brzegowy: jeśli kolor komórki początkowej jest już taki sam jak nowy kolor, należy natychmiast zwrócić wynik, aby uniknąć nieskończonej rekurencji.
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]]Maksymalny obszar wyspy
Maksymalny obszar wyspy (LeetCode #695) rozszerza zliczanie wysp: dla każdej wyspy należy zwrócić rozmiar największej z nich. Podczas wypełniania obszaru metodą DFS należy zliczać oznaczane komórki. DFS zwraca rozmiar bieżącej wyspy, a Państwo śledzą maksimum dla wszystkich wysp. To proste rozszerzenie wzorca składowych spójnych.
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)) # 6Przepływ wody do Pacyfiku i Atlantyku
Przepływ wody do Pacyfiku i Atlantyku (LeetCode #417) wymaga wskazania komórek, z których woda może przepłynąć zarówno do oceanu Spokojnego (górna/lewa krawędź), jak i do Atlantyku (dolna/prawa krawędź). Zamiast symulować spływanie wody w dół, należy użyć odwrotnego DFS: woda płynie w górę od strony oceanów. Wykonaj dwa przejścia DFS — jedno od granic Pacyfiku, drugie od granic Atlantyku — zbierając osiągalne komórki. Część wspólna tych zbiorów jest odpowiedzią.
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]]))Iteracyjny DFS dla składowych spójnych
Należy użyć iteracyjnego DFS (z jawnym stosem), aby uniknąć limitu rekurencji języka Python dla dużych siatek. Wersja iteracyjna jest równoważna rekurencyjnemu DFS, ale korzysta ze stosu zamiast stosu wywołań. Umieść węzeł początkowy na stosie, następnie zdejmuj węzły, oznaczaj je jako odwiedzone i umieszczaj na stosie nieodwiedzonych sąsiadów. Dzięki temu można bezpiecznie obsługiwać siatki zawierające nawet miliony komórek, podczas gdy rekurencyjny DFS doprowadziłby do przepełnienia stosu.
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)])) # 3Otoczone regiony
Otoczone regiony (LeetCode #130) wyszukuje wszystkie regiony „O” całkowicie otoczone granicami „X”. Region NIE zostaje przechwycony, jeśli którakolwiek z jego komórek „O” dotyka krawędzi planszy. Sztuczka polega na tym, aby zamiast bezpośrednio wyszukiwać otoczone regiony, wykonać DFS od wszystkich brzegowych komórek „O” i oznaczyć wszystko, co jest osiągalne, jako bezpieczne. Następnie należy odwrócić oznaczenia: wszystkie pozostałe komórki „O” są otoczone i stają się „X”, a bezpieczne komórki zostają przywrócone do „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, OZliczanie podwysp
Zliczanie podwysp (LeetCode #1905) wyszukuje wyspy w grid2, które w całości zawierają się w wyspie w grid1. Wykonaj DFS od każdej komórki „1” w grid2: wyspa jest podwyspą, jeśli każda odwiedzona przez nią komórka jest również „1” w grid1. Sztuczka polega na odwiedzeniu WSZYSTKICH komórek wyspy (aby oznaczyć je jako zbadane), a jednocześnie sprawdzeniu, czy WSZYSTKIE z nich były również „1” w grid1. Nie należy przerywać po napotkaniu pierwszego „0” w grid1 — w przeciwnym razie pozostałe komórki tej samej wyspy nie zostałyby oznaczone.
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 a BFS dla składowych spójnych
Zarówno DFS, jak i BFS poprawnie znajdują wszystkie składowe spójne, zachowując tę samą złożoność czasową O(V + E) i pamięciową O(V). DFS jest prostszy do rekurencyjnej implementacji w zadaniach dotyczących składowych spójnych, natomiast BFS jest preferowany, gdy potrzebne są również informacje o najkrótszych ścieżkach. W zadaniach na siatkach DFS lepiej wykorzystuje pamięć podręczną, ponieważ przed rozpoczęciem cofania zagłębia się w jednym kierunku, uzyskując sekwencyjny dostęp do sąsiednich obszarów pamięci.
# 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')Wyspy z ograniczeniami: kształty i obwody
Obwód wyspy (LeetCode #463) zlicza całkowity obwód jedynej wyspy w siatce. Dla każdej komórki lądu („1”) należy dodać 4 do obwodu, a następnie odjąć 2 za każdą sąsiednią komórkę lądu (wspólne krawędzie). To podejście oparte na wzorze i działające w czasie O(mn) nie wymaga DFS — jednak zrozumienie, że jest ono równoważne DFS-owi zliczającemu krawędzie graniczne, wzmacnia związek między zadaniami na siatkach a rozumowaniem grafowym.
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)) # 16Szybki test
Sprawdź swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: znajdowania składowych spójnych za pomocą DFS ze śledzeniem odwiedzonych węzłów, stosowania zliczania wysp i wypełniania obszaru jako podstawowych zastosowań na dwuwymiarowych siatkach, a także zaawansowanych wzorców, takich jak odwrotny DFS od brzegów (otoczone regiony) i wiele przejść DFS ze śledzeniem ograniczeń (podwyspy). Następnie zajmiemy się wykrywaniem cykli w grafach skierowanych i nieskierowanych.
Często zadawane pytania
Czy lekcja „DFS: spójne składowe i flood fill” jest bezpłatna?
Tak — pełny tekst „DFS: spójne składowe i flood fill” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „DFS: spójne składowe i flood fill”?
Zastosują Państwo DFS do zliczania spójnych składowych, rozwiążą zadanie number-of-islands na siatce 2D i zaimplementują flood fill do przetwarzania obrazów. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „DFS: spójne składowe i flood fill”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Reprezentacje grafów i przygotowanie przejść
- BFS: najkrótsza ścieżka i przejście poziomami
- DFS: spójne składowe i flood fill
- Wykrywanie cykli w grafach skierowanych i nieskierowanych