DFS : composantes connexes et remplissage
Appliquez DFS pour compter les composantes connexes, résolvez number-of-islands sur une grille 2D et implémentez le remplissage pour le traitement d’images.
DFS : composantes connexes et remplissage est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Définition des composantes connexes
Une composante connexe d’un graphe non orienté est un ensemble maximal de sommets tel qu’il existe un chemin entre chaque paire de sommets de l’ensemble. Un même graphe peut comporter plusieurs composantes déconnectées. La recherche des composantes connexes constitue la base de nombreux problèmes de graphes : le regroupement, la fusion, le comptage des îles et la consolidation de comptes se réduisent tous à cette opération 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}')Compter les composantes connexes avec DFS
Parcourez tous les nœuds. Pour chaque nœud non visité, lancez un DFS afin de marquer comme visités tous les nœuds accessibles. Chaque lancement de DFS correspond à la découverte d’une nouvelle composante. Comptez le nombre de lancements de DFS pour obtenir le nombre de composantes. Cet algorithme en O(V + E) fonctionne correctement que le graphe soit connexe ou non.
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)])) # 2Nombre d’îles
Nombre d’îles (LeetCode #200) est le problème classique des composantes connexes sur une grille 2D. Chaque cellule « 1 » appartient à une île ; les cellules « 1 » adjacentes (haut/bas/gauche/droite) forment la même île. Comptez le nombre d’îles distinctes à l’aide de DFS : parcourez toutes les cellules et, lorsque vous trouvez un « 1 » non visité, lancez un DFS qui marque toutes les cellules « 1 » connectées (remplissage par propagation), puis incrémentez le compteur.
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)) # 3Algorithme de remplissage par propagation
Remplissage par propagation (LeetCode #733) remplace toutes les cellules connectées d’une couleur donnée, à partir d’une cellule initiale, par une nouvelle couleur — exactement comme l’outil pot de peinture des éditeurs d’images. Utilisez DFS : à partir du pixel source, recolorez récursivement tous les voisins qui correspondent à la couleur d’origine. Le principal cas limite est le suivant : si la couleur de la cellule initiale est déjà égale à la nouvelle couleur, renvoyez immédiatement le résultat afin d’éviter une récursion infinie.
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]]Aire maximale d'une île
Aire maximale d'une île (LeetCode n° 695) étend le comptage des îles : pour chaque île, renvoyez la taille de la plus grande. Lors du remplissage par propagation avec DFS, comptez les cellules que vous marquez. Le parcours DFS renvoie la taille de l'île actuelle, et vous suivez le maximum parmi toutes les îles. Il s'agit d'une simple extension du schéma des composantes connexes.
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)) # 6Flux d'eau du Pacifique et de l'Atlantique
Flux d'eau du Pacifique et de l'Atlantique (LeetCode n° 417) demande quelles cellules peuvent s'écouler vers les deux océans, le Pacifique (bords supérieur et gauche) et l'Atlantique (bords inférieur et droit). Au lieu de simuler l'écoulement de l'eau vers le bas, utilisez un DFS inversé : l'eau s'écoule vers le haut depuis les océans. Effectuez deux parcours DFS — l'un depuis les frontières du Pacifique, l'autre depuis celles de l'Atlantique — et rassemblez les cellules accessibles. L'intersection constitue la réponse.
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 itératif pour les composantes connexes
Utilisez un DFS itératif (avec une pile explicite) pour éviter la limite de récursion de Python sur les grandes grilles. La version itérative est équivalente au DFS récursif, mais utilise une pile au lieu de la pile d'appels. Empilez le nœud de départ, puis retirez-le de la pile, marquez-le comme visité et empilez ses voisins non visités. Cette méthode gère en toute sécurité des grilles contenant jusqu'à des millions de cellules, là où un DFS récursif provoquerait un débordement de pile.
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)])) # 3Régions entourées
Régions entourées (LeetCode n° 130) détecte toutes les régions « O » complètement entourées de bordures « X ». Une région n'est pas capturée (NOT) si l'une de ses cellules « O » touche le bord de la grille. L'astuce consiste à ne pas chercher directement les régions entourées : effectuez plutôt un DFS depuis toutes les cellules « O » situées sur le bord et marquez comme sûres toutes celles qui sont accessibles. Inversez ensuite la transformation : toutes les cellules « O » restantes sont entourées et deviennent « X », tandis que les cellules sûres redeviennent « 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, OCompter les sous-îles
Compter les sous-îles (LeetCode n° 1905) trouve les îles de la grille 2 qui sont entièrement contenues dans une île de la grille 1. Effectuez un DFS depuis chaque cellule « 1 » de la grille 2 : une île est une sous-île si chacune des cellules visitées est également « 1 » dans la grille 1. L'astuce consiste à visiter toutes les cellules (ALL) de l'île pour les marquer comme explorées, tout en vérifiant qu'elles sont toutes également « 1 » dans la grille 1. N'interrompez pas le parcours au premier « 0 » de la grille 1 : vous ne marqueriez pas les autres cellules de la même île.
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 contre BFS pour les composantes connexes
DFS et BFS trouvent correctement toutes les composantes connexes, avec la même complexité temporelle en O(V + E) et spatiale en O(V). Une mise en œuvre récursive de DFS est plus simple pour les problèmes de composantes connexes, tandis que BFS est préférable lorsque vous avez également besoin d'informations sur les plus courts chemins. Dans les problèmes sur les grilles, DFS est plus efficace pour le cache, car il explore une direction en profondeur avant de revenir en arrière et accède ainsi séquentiellement à des emplacements mémoire proches.
# 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')Îles sous contraintes : formes et périmètres
Périmètre de l'île (LeetCode n° 463) compte le périmètre total de l'unique île d'une grille. Pour chaque cellule terrestre (« 1 »), ajoutez 4 au périmètre, puis soustrayez 2 pour chaque cellule terrestre adjacente (arêtes partagées). Cette approche fondée sur une formule en O(mn) ne nécessite aucun DFS ; mais comprendre qu'elle équivaut à un DFS qui compte les arêtes de frontière renforce le lien entre les problèmes sur les grilles et le raisonnement sur les graphes.
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)) # 16Vérification rapide
Vérifiez votre compréhension des concepts de structures de données & algorithmes — préparation aux entretiens de programmation de cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : les composantes connexes avec DFS et le suivi des cellules visitées, le nombre d'îles et le remplissage par propagation comme applications classiques aux grilles 2D, ainsi que des schémas avancés comme le DFS inversé depuis les frontières (régions entourées) et le DFS multiple avec suivi de contraintes (sous-îles). Nous abordons ensuite la détection des cycles dans les graphes orientés et non orientés.
Questions Fréquemment Posées
La leçon « DFS : composantes connexes et remplissage » est-elle gratuite ?
Oui — le texte complet de « DFS : composantes connexes et remplissage » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « DFS : composantes connexes et remplissage » ?
Appliquez DFS pour compter les composantes connexes, résolvez number-of-islands sur une grille 2D et implémentez le remplissage pour le traitement d’images. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « DFS : composantes connexes et remplissage » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Représentations des graphes et préparation des parcours
- BFS : plus court chemin et parcours par niveaux
- DFS : composantes connexes et remplissage
- Détection de cycles dans les graphes orientés et non orientés