DFS: componenti connesse e flood fill
Applichi DFS per contare le componenti connesse, risolva number-of-islands su una griglia 2D e implementi flood fill per l'elaborazione delle immagini
DFS: componenti connesse e flood fill è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Definizione di componente connessa
Una componente connessa in un grafo non orientato è un insieme massimale di vertici tale che esiste un cammino tra ogni coppia di vertici dell'insieme. Un singolo grafo può avere più componenti disconnesse. Trovare le componenti connesse è alla base di molti problemi sui grafi: raggruppamento, fusione, conteggio delle isole e consolidamento degli account sono tutti riconducibili a questo costrutto fondamentale.
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}')Contare le componenti connesse con DFS
Scorra tutti i nodi. Per ogni nodo non visitato, avvii una DFS per contrassegnare come visitati tutti i nodi raggiungibili. Ogni avvio di DFS corrisponde alla scoperta di una nuova componente. Conti il numero di avvii di DFS per ottenere il numero di componenti. Questo algoritmo O(V + E) funziona correttamente sia che il grafo sia connesso, sia che non lo sia.
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)])) # 2Numero di isole
Number of Islands (LeetCode #200) è il problema canonico delle componenti connesse su una griglia 2D. Ogni cella '1' appartiene a un'isola; le celle '1' adiacenti (sopra/sotto/sinistra/destra) formano la stessa isola. Conti il numero di isole distinte utilizzando DFS: scorra tutte le celle e, quando trova una cella '1' non visitata, avvii una DFS che contrassegni tutte le celle '1' connesse (flood fill), quindi incrementi il conteggio.
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)) # 3Algoritmo Flood Fill
Flood Fill (LeetCode #733) sostituisce tutte le celle connesse di un determinato colore con un nuovo colore, esattamente come lo strumento secchiello degli editor di immagini. Utilizzi DFS: partendo dal pixel sorgente, ricolori ricorsivamente tutti i nodi adiacenti che corrispondono al colore originale. Il caso limite fondamentale è il seguente: se il colore della cella iniziale è già uguale al nuovo colore, restituisca immediatamente il risultato per evitare la ricorsione infinita.
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]]Area massima dell'isola
Max Area of Island (LeetCode #695) estende il conteggio delle isole: per ogni isola, restituisce la dimensione della più grande. Durante il flood fill con DFS, si contano le celle contrassegnate. La DFS restituisce la dimensione dell'isola corrente e si tiene traccia del massimo tra tutte le isole. Si tratta di una semplice estensione del modello delle componenti connesse.
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)) # 6Flusso d'acqua tra Pacifico e Atlantico
Pacific Atlantic Water Flow (LeetCode #417) chiede quali celle possano far defluire l'acqua sia verso l'oceano Pacifico (bordi superiore e sinistro) sia verso l'Atlantico (bordi inferiore e destro). Invece di simulare l'acqua che scorre verso il basso, si utilizza la DFS inversa: si immagina che l'acqua scorra verso l'alto a partire dagli oceani. Si eseguono due passate DFS: una dai bordi del Pacifico e una dai bordi dell'Atlantico, raccogliendo le celle raggiungibili. L'intersezione è la risposta.
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]]))DFS iterativa per le componenti connesse
Si utilizza la DFS iterativa (con uno stack esplicito) per evitare il limite di ricorsione di Python sulle griglie di grandi dimensioni. La versione iterativa è equivalente alla DFS ricorsiva, ma utilizza uno stack invece dello stack delle chiamate. Si inserisce il nodo iniziale, quindi lo si estrae, lo si contrassegna come visitato e si inseriscono i vicini non visitati. Questo consente di gestire in sicurezza griglie fino a milioni di celle, mentre la DFS ricorsiva causerebbe un overflow dello stack.
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)])) # 3Regioni circondate
Surrounded Regions (LeetCode #130) individua tutte le regioni di 'O' completamente circondate da bordi di 'X'. Una regione NON viene individuata se una qualsiasi delle sue celle 'O' tocca il bordo della griglia. Il trucco consiste nel non cercare direttamente le regioni circondate, ma nell'eseguire una DFS da tutte le celle 'O' sul bordo e contrassegnare come sicuro tutto ciò che è raggiungibile. Poi si esegue la trasformazione: tutte le celle 'O' rimanenti sono circondate e diventano 'X', mentre le celle sicure vengono ripristinate a '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, OConteggio delle sottoisole
Count Sub-Islands (LeetCode #1905) individua le isole di grid2 interamente contenute in un'isola di grid1. Si esegue una DFS da ogni cella '1' di grid2: un'isola è una sottoisola se ogni cella visitata è anch'essa '1' in grid1. Il trucco consiste nel visitare TUTTE le celle dell'isola, per contrassegnarle come esplorate, tenendo però traccia del fatto che TUTTE siano anche '1' in grid1. Non bisogna interrompere la ricerca al primo '0' in grid1: si ometterebbe il contrassegno delle altre celle della stessa isola.
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 e BFS a confronto per le componenti connesse
Sia la DFS sia la BFS individuano correttamente tutte le componenti connesse, con la stessa complessità temporale O(V + E) e spaziale O(V). La DFS è più semplice da implementare in modo ricorsivo per i problemi sulle componenti connesse, mentre la BFS è preferibile quando serve anche ottenere informazioni sui cammini minimi. Nei problemi sulle griglie, la DFS è più favorevole alla cache perché esplora in profondità una direzione prima di tornare indietro, accedendo in sequenza a posizioni di memoria vicine.
# 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')Isole con vincoli: forme e perimetri
Island Perimeter (LeetCode #463) calcola il perimetro totale dell'unica isola presente in una griglia. Per ogni cella di terra ('1'), si aggiunge 4 al perimetro, quindi si sottrae 2 per ogni cella di terra adiacente (lato condiviso). Questo approccio basato su una formula, con complessità O(mn), non richiede la DFS; comprendere però che è equivalente a una DFS che conta i lati di confine rafforza il collegamento tra i problemi sulle griglie e il ragionamento sui grafi.
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)) # 16Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato a individuare le componenti connesse tramite DFS e tracciamento dei nodi visitati, a utilizzare il conteggio delle isole e il flood fill come applicazioni canoniche alle griglie 2D e ad applicare modelli avanzati come la DFS inversa dai bordi (regioni circondate) e la DFS multipla con tracciamento dei vincoli (sottoisole). Ora affronteremo l'individuazione dei cicli nei grafi diretti e non diretti.
Domande Frequenti
La lezione «DFS: componenti connesse e flood fill» è gratuita?
Sì — il testo completo di «DFS: componenti connesse e flood fill» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «DFS: componenti connesse e flood fill»?
Applichi DFS per contare le componenti connesse, risolva number-of-islands su una griglia 2D e implementi flood fill per l'elaborazione delle immagini Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «DFS: componenti connesse e flood fill»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Rappresentazioni dei grafi e configurazione dei percorsi
- BFS: percorso più breve e visita per livelli
- DFS: componenti connesse e flood fill
- Rilevamento dei cicli nei grafi diretti e non diretti