グラフ表現と走査の準備
隣接リストで有向・無向グラフを構築し、dequeでBFSを、スタックまたは再帰でDFSを初期化し、訪問済み管理を行います。
「グラフ表現と走査の準備」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
グラフとは
グラフとは、辺で結ばれたノード（頂点）の集合です。木とは異なり、グラフにはサイクル、ノード間の複数の経路、非連結な連結成分が存在することがあります。グラフは、ソーシャルネットワーク、道路地図、依存関係の木構造、Webページのリンクなど、現実世界のシステムをモデル化します。ほぼすべての本格的なシステム設計やアルゴリズムの面接でグラフが扱われるため、その表現と走査を身につけることが重要です。
# Graph terminology:
# - V: set of vertices (nodes)
# - E: set of edges
# - Directed graph: edges have direction (A -> B but not B -> A)
# - Undirected graph: edges are bidirectional
# - Weighted graph: edges have costs/weights
# - Cyclic: contains at least one cycle
# - Acyclic: no cycles (DAG = Directed Acyclic Graph)
# - Connected: every node reachable from every other
# - Disconnected: multiple isolated components
print('Graph: nodes + edges, directed/undirected, weighted/unweighted')隣接リスト表現
隣接リストは、各ノードに隣接するノードの一覧を格納します。Pythonでは、各ノードを隣接ノードのリストに対応付けるdictを使用します。これは面接問題で最も一般的な表現です。空間計算量は O(V + E)（疎グラフで効率的）、隣接ノードの反復は O(degree)、ハッシュセットを使う形式なら隣接確認は平均 O(1) です。LeetCodeのグラフ問題の多くはこの形式を使用します。
from collections import defaultdict
# Build an undirected graph
def build_undirected(edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # both directions
return graph
edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
graph = build_undirected(edges)
print(dict(graph))
# {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}
# Directed graph: only one direction
def build_directed(edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v) # only u -> v
return graph隣接行列表現
隣接行列は、辺が i から j へ存在する場合に matrix[i][j] = 1（または辺の重み）、存在しない場合に 0 となる V×V の2次元配列です。辺の検索を O(1) で行える一方、辺の数に関係なく O(V²) の空間を使用するため、疎グラフでは非効率です。グラフが密である場合や、Floyd-Warshall法による全点対最短経路のように、辺の存在を高速に確認することが重要な場合に適しています。
# Adjacency matrix for 5 nodes
V = 5
matrix = [[0] * V for _ in range(V)]
edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # undirected
# Print the matrix:
for row in matrix:
print(row)
# Neighbour check: O(1)
print('Edge 0-2:', bool(matrix[0][2])) # True
print('Edge 0-4:', bool(matrix[0][4])) # False
# Space: O(V^2) vs adjacency list O(V+E)
# Dense graph: matrix often better; sparse: list better辺リスト表現
辺リストは最も単純な表現で、重みを付ける場合もある (source, destination) タプルのリストです。空間計算量は O(E) で、すべての辺を簡単に反復できます。ただし、あるノードの隣接ノードを見つけるにはすべての辺を走査する必要があり、O(E) かかります。辺リストは、Bellman-Ford法（すべての辺を n-1 回緩和）やKruskalの最小全域木アルゴリズムのように、すべての辺を決まった回数だけ反復するグラフアルゴリズムで使用されます。
# Weighted edge list: (source, destination, weight)
edge_list = [
(0, 1, 4),
(0, 2, 1),
(1, 3, 1),
(2, 3, 5),
(3, 4, 3)
]
# Useful for:
# Bellman-Ford: iterate all edges n-1 times
# Kruskal's MST: sort by weight then union-find
# Sort by weight for Kruskal:
edge_list_sorted = sorted(edge_list, key=lambda e: e[2])
print('Sorted by weight:', edge_list_sorted)
# Finding neighbours: O(E) scan -- inefficient for traversal
node_0_neighbors = [v for u, v, w in edge_list if u == 0]
print('Node 0 neighbors:', node_0_neighbors)BFSの準備：キューと訪問済み集合
BFS（幅優先探索）はキューを使用して、グラフをレベルごとに探索します。重要な要素は、巡回グラフでノードを再訪問しないようにする訪問済み集合です。訪問済み集合がないと、巡回グラフに対するBFSは無限ループになります。標準的な準備では、始点ノードをキューに追加して訪問済みとしてマークし、その後、キューから取り出して処理し、未訪問の隣接ノードを追加する操作を繰り返します。
from collections import deque
def bfs(graph, start):
visited = {start} # mark source as visited
queue = deque([start]) # initialise queue
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour) # mark BEFORE enqueue
queue.append(neighbour)
return order
from collections import defaultdict
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
graph[u].append(v); graph[v].append(u)
print(bfs(graph, 0)) # [0, 1, 2, 3, 4]DFSの準備：スタックまたは再帰
DFS（深さ優先探索）は、各分岐を可能な限り深く探索してから後戻りします。再帰的（コールスタックを使用）または反復的（明示的なスタックを使用）に実装できます。巡回グラフでは、どちらにも訪問済み集合が必要です。再帰的なDFSと同じ探索順序にするには、反復版で隣接ノードを逆順にスタックへ追加します。ただし、2つの実装では探索順序が異なる場合があります。
def dfs_recursive(graph, node, visited=None, order=None):
if visited is None: visited = set(); order = []
visited.add(node)
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
dfs_recursive(graph, neighbour, visited, order)
return order
def dfs_iterative(graph, start):
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop()
if node in visited: continue
visited.add(node)
order.append(node)
for neighbour in reversed(graph[node]): # reverse for same order as recursive
if neighbour not in visited:
stack.append(neighbour)
return order
print('Recursive DFS:', dfs_recursive(graph, 0))
print('Iterative DFS:', dfs_iterative(graph, 0))BFSとDFSの使い分け
重みなしグラフで最短経路（辺の数が最小の経路）が必要な場合や、ノードをレベルごとに処理する必要がある場合はBFSを選択します。到達可能なすべてのノードの探索、巡回の検出、連結成分の発見、トポロジカルソート、すべての経路の列挙が必要な場合はDFSを選択します。実際には、「最短／最小ホップ数」にはBFS、「存在確認／到達可能性／列挙」にはDFSを使用します。
# BFS use cases:
# - Shortest path in unweighted graph (fewest edges)
# - Level-order traversal
# - Word ladder (minimum transformations)
# - Clone graph
# DFS use cases:
# - Connected components (flood fill)
# - Cycle detection
# - Topological sort
# - All paths between two nodes
# - Maze solving (any path)
# - N-queens, Sudoku (backtracking)
# Both: O(V + E) time, O(V) space for visited
print('BFS: shortest hops | DFS: existence and enumeration')LeetCodeの入力形式からグラフを構築する
LeetCodeのグラフ問題には、さまざまな入力形式があります。辺リスト：[[0,1],[0,2]] — 隣接リストを構築します。インデックスベースの隣接リスト：graph[i]は i の隣接ノードのリストです。グリッド／行列：セルをノード、上下左右に隣接するセルを隣接ノードとする m×n の2次元配列です。子を持つノード：Node(val, neighbors)のようなカスタムクラスです。これらの形式を見分け、最初の手順として隣接リストに変換します。
# Format 1: edge list -> adjacency list
def edges_to_adj(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
return graph
# Format 2: 2D grid -> adjacency (implicit)
# Neighbours of (r, c): (r-1,c), (r+1,c), (r,c-1), (r,c+1)
DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
def grid_neighbours(grid, r, c):
rows, cols = len(grid), len(grid[0])
return [(r+dr, c+dc) for dr, dc in DIRS
if 0 <= r+dr < rows and 0 <= c+dc < cols]
grid = [[1,1,0],[0,1,1],[1,0,0]]
print('Neighbours of (0,0):', grid_neighbours(grid, 0, 0))
print('Neighbours of (1,1):', grid_neighbours(grid, 1, 1))グリッドで訪問済みを記録する
グリッド問題で訪問済みセルを追跡する方法は2つあります。方法A：(row, col)タプルのvisited集合を別に使用します。追加の空間計算量は O(m*n) です。方法B：グリッドをインプレースで変更し、訪問済みセルを特別な値（例：'#'や2）でマークします。必要に応じて、後で元に戻します。インプレース方式は追加の空間を O(1) に抑えられ、フラッドフィルやNumber of Islandsの問題でよく使われます。
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 as 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'],
['1','1','0','0'],
['0','0','1','0'],
['0','0','0','1']]
print(num_islands(grid)) # 3複数の始点でBFSを初期化する
マルチソースBFSは、すべての始点ノードを訪問済みとしてキューに初期化し、複数のノードから同時に開始します。「最寄りの 0 からの距離」、「腐ったオレンジ」、「Walls and Gates」のように、いずれかの始点ノードからの最短距離を求める問題で使用します。マルチソースBFSの計算量は O(V + E) で、単一始点の場合と同じです。各ノードは依然として最大1回しか訪問されないためです。
from collections import deque
def rotting_oranges(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Multi-source: all rotten oranges start at time=0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # (row, col, time)
elif grid[r][c] == 1:
fresh += 1
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
time = 0
while queue:
r, c, t = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1:
grid[nr][nc] = 2 # mark rotten
fresh -= 1
queue.append((nr, nc, t+1))
time = t + 1
return time if fresh == 0 else -1
print(rotting_oranges([[2,1,1],[1,1,0],[0,1,1]])) # 4グラフの密度と表現の選択
隣接リストと隣接行列のどちらを選ぶかは、グラフの密度（E/V² の比率）によって決まります。疎グラフ（E << V²）では、隣接行列の O(V²) に対して空間計算量が O(V+E) となる隣接リストが有利です。密グラフ（E ≈ V²）では、隣接リストの O(degree) に対して辺の検索が O(1) となる隣接行列が有利です。面接問題では、ほとんどの問題が疎グラフを扱うため、隣接リストがほぼ常に適切な選択です。
# Graph density comparison:
# Sparse: social network (V=1B users, avg 200 friends)
# E = 200 * 1B = 200B << V^2 = 10^18 -> adjacency list
# Dense: complete graph (every node connected to every other)
# E = V*(V-1)/2 ≈ V^2 -> adjacency matrix
# Interview rule of thumb:
# - Default to adjacency list (defaultdict(list))
# - Use matrix only when asked about dense graph or O(1) edge lookup
# - Grid problems: use implicit adjacency (4-directional neighbours)
print('Sparse graph (E << V^2): use adjacency list')
print('Dense graph (E ~ V^2): consider adjacency matrix')理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、3つのグラフ表現（隣接リスト、隣接行列、辺リスト）とそれぞれの使い分け、巡回グラフでの無限ループを防ぐためのBFSとDFSの準備（訪問済み集合を含む）、さらにグリッドのインプレースマーキングやマルチソースBFSなどの実践的なパターンを学びました。次は、BFSを使って最短経路とレベルごとの探索を行います。
よくある質問
「グラフ表現と走査の準備」レッスンは無料ですか？
はい。「グラフ表現と走査の準備」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「グラフ表現と走査の準備」で何を学びますか？
隣接リストで有向・無向グラフを構築し、dequeでBFSを、スタックまたは再帰でDFSを初期化し、訪問済み管理を行います。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「グラフ表現と走査の準備」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。