DFS：連結成分とflood fill
DFSを適用して連結成分を数え、2Dグリッドのnumber-of-islandsを解き、画像処理用のflood fillを実装します。
「DFS：連結成分とflood fill」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
連結成分の定義
無向グラフにおける連結成分とは、その集合内の任意の2つの頂点の間に経路が存在するような、極大な頂点集合です。1つのグラフが、互いに分離した複数の連結成分を持つ場合もあります。連結成分の発見は、多くのグラフ問題の基礎です。グループ化、統合、島の個数の計算、アカウントの統合は、いずれもこの基本処理に帰着できます。
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}')DFSで連結成分を数える
すべてのノードを反復します。未訪問のノードごとにDFSを開始し、そこから到達可能なすべてのノードを訪問済みとしてマークします。DFSを開始するたびに、新しい連結成分を1つ発見したことになります。DFSを開始した回数を数えることで、連結成分の数を求められます。この O(V + E) のアルゴリズムは、グラフが連結しているかどうかに関係なく正しく動作します。
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）は、2次元グリッド上で連結成分を求める典型的な問題です。各 '1' セルは島に属し、上下左右に隣接する '1' セルは同じ島を形成します。DFSを使って異なる島の数を数えます。すべてのセルを反復し、未訪問の '1' を見つけたら、その '1' と連結しているすべてのセルをマークするDFS（フラッドフィル）を開始し、その後カウントを増やします。
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)) # 3フラッドフィルアルゴリズム
Flood Fill（LeetCode #733）は、指定した始点と同じ色で連結しているすべてのセルを新しい色に置き換える問題です。画像編集ソフトの塗りつぶしツールと同じ処理です。DFSを使用し、始点ピクセルから開始して、元の色と一致するすべての隣接セルを再帰的に塗り替えます。重要なエッジケースは、始点セルの色がすでに新しい色と同じ場合です。この場合は、無限再帰を避けるためにすぐに返します。
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]]島の最大面積
島の最大面積（LeetCode #695）は、島の数え上げを拡張した問題です。それぞれの島について、その中で最大の島の大きさを返します。DFSによるフラッドフィルでは、マークしたセルを数えます。DFSは現在の島のサイズを返し、すべての島の中で最大値を追跡します。これは連結成分のパターンを単純に拡張したものです。
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)) # 6太平洋と大西洋へ流れる水
太平洋と大西洋へ流れる水（LeetCode #417）は、太平洋（上端／左端）と大西洋（下端／右端）の両方へ水が流れ込むセルを求める問題です。水が下向きに流れる様子をシミュレートする代わりに、逆向きDFSを使います。つまり、海から水が上向きに流れると考えます。太平洋の境界から1回、大西洋の境界から1回、合計2回のDFSを行い、到達可能なセルを集めます。その共通部分が答えです。
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
大きなグリッドでPythonの再帰上限に達するのを避けるには、反復DFS（明示的なスタックを使うDFS）を使用します。反復版は再帰版DFSと同等ですが、コールスタックの代わりにスタックを使用します。開始ノードをプッシュし、次にポップして訪問済みとしてマークし、未訪問の隣接ノードをプッシュします。これにより、再帰DFSではスタックオーバーフローが発生するような数百万セルのグリッドも安全に処理できます。
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)])) # 3囲まれた領域
囲まれた領域（LeetCode #130）は、'X'の境界によって完全に囲まれた'O'の領域をすべて特定する問題です。'O'のセルのいずれかが盤面の端に接している場合、その領域は捕捉されません。ポイントは、囲まれた領域を直接探すのではなく、境界上にあるすべての'O'のセルからDFSを行い、到達可能なセルをすべて安全なセルとしてマークすることです。その後で反転を行います。残った'O'のセルは囲まれているため'X'に変え、安全なセルは'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, Oサブアイランドの数え上げ
サブアイランドの数え上げ（LeetCode #1905）は、grid2の島のうち、grid1の島に完全に含まれているものを見つける問題です。grid2の各'1'セルからDFSを行い、訪問したすべてのセルがgrid1でも'1'である場合、その島はサブアイランドです。ポイントは、島のすべてのセルを訪問して探索済みとしてマークしながら、それらがすべてgrid1でも'1'だったかどうかを追跡することです。grid1で最初の'0'が見つかった時点で処理を短絡してはいけません。そうすると、同じ島に属する他のセルをマークし損ないます。
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]])) # 1連結成分におけるDFSとBFS
DFSとBFSはどちらも、すべての連結成分を正しく見つけられ、時間計算量は同じO(V + E)、空間計算量は同じO(V)です。連結成分の問題では、再帰によるDFSのほうが実装は簡単ですが、最短経路の情報も必要な場合はBFSが好まれます。グリッドの問題では、DFSは1方向に深く探索してからバックトラックするため、近接したメモリ領域を順番にアクセスでき、キャッシュ効率が高くなります。
# 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')制約付きの島：形状と周囲長
島の周囲長（LeetCode #463）は、グリッド内にある1つの島の周囲長の合計を数える問題です。各陸地セル（'1'）について周囲長に4を加え、隣接する陸地セルごとに2を引きます（共有する辺の分です）。このO(mn)の公式に基づく方法ではDFSは必要ありません。しかし、これが境界の辺を数えるDFSと同等であることを理解すると、グリッドの問題とグラフによる考え方のつながりがより明確になります。
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)) # 16理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、訪問済み管理を伴うDFSによる連結成分、2Dグリッドの代表的な応用である島の数え上げとフラッドフィル、さらに境界からの逆向きDFS（囲まれた領域）や制約を追跡する複数DFS（サブアイランド）といった高度なパターンを学びました。次は、有向グラフと無向グラフにおけるサイクル検出に取り組みます。
よくある質問
「DFS：連結成分とflood fill」レッスンは無料ですか？
はい。「DFS：連結成分とflood fill」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「DFS：連結成分とflood fill」で何を学びますか？
DFSを適用して連結成分を数え、2Dグリッドのnumber-of-islandsを解き、画像処理用のflood fillを実装します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「DFS：連結成分とflood fill」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- グラフ表現と走査の準備
- BFS：最短経路とレベル走査
- DFS：連結成分とflood fill
- 有向・無向グラフの循環検出