图的表示与遍历准备
使用邻接表构建有向图和无向图，用 deque 初始化 BFS，用栈或递归实现 DFS，并处理访问记录。
图的表示与遍历准备 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
什么是图
图是由边连接起来的节点（顶点）集合。与树不同，图可以包含环、节点之间的多条路径，以及不连通的组件。图可以对社交网络、道路地图、依赖关系树和网页链接等现实世界的系统进行建模。几乎所有复杂的系统设计和算法面试都会涉及图；掌握图的表示和遍历方式至关重要。
# 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(度数)，使用哈希集合变体检查邻接关系的平均时间为 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邻接矩阵表示
邻接矩阵是一个 V×V 的二维数组：如果存在从 i 到 j 的边，则 matrix[i][j] = 1（或存储边的权重），否则为 0。它支持 O(1) 的边查询，但无论边的数量多少都需要 O(V²) 的空间——对稀疏图而言很浪费。当图是稠密的（边很多），或快速检查边是否存在非常重要时，例如使用弗洛伊德-沃舍尔算法求全源最短路径时，通常优先选择邻接矩阵。
# 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边列表表示
边列表是最简单的表示方式：仅使用一个由（源节点、目标节点）元组组成的列表，也可以选择为元组添加权重。它需要 O(E) 的空间，并且易于遍历所有边。不过，查找某个节点的邻居需要扫描所有边，时间复杂度为 O(E)。边列表用于需要完整遍历所有边的图算法，例如贝尔曼-福特算法（将所有边进行松弛 n-1 次）和克鲁斯卡尔最小生成树算法。
# 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 的遍历顺序，不过两种实现的探索顺序可能有所不同。
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 的二维数组，其中单元格是节点，上下左右相邻的单元格是邻居。带子节点的 Node：类似 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))在网格中标记已访问
对于网格问题，有两种跟踪已访问单元格的方法。方法 A：使用单独的 visited 集合存储 (row, col) 元组——需要 O(m*n) 的额外空间。方法 B：通过使用哨兵值（例如 '#' 或 2）标记已访问单元格，原地修改网格，并在需要时之后恢复这些单元格。原地方法只使用 O(1) 的额外空间，常用于泛洪填充和岛屿数量问题。
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 的距离”“腐烂的橘子”和“墙与门”等问题，这些问题需要求某个节点到任意源节点的最短距离。多源 BFS 的时间复杂度为 O(V + E)，与单源 BFS 相同，因为每个节点仍然最多只会被访问一次。
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+E)，而矩阵需要 O(V²)。稠密图（E ≈ V²）适合使用邻接矩阵：边查询为 O(1)，而邻接表需要 O(度数)。对于面试题，邻接表几乎总是正确选择，因为大多数问题涉及稀疏图。
# 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')快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中您学习了：三种图表示方式（邻接表、邻接矩阵、边列表）及其各自的适用场景；使用已访问集合设置BFS 和 DFS，以避免在有环图中无限循环；以及原地标记网格和多源 BFS等实用模式。接下来，我们将应用 BFS 查找最短路径并进行逐层遍历。
常见问题解答
「图的表示与遍历准备」课时是免费的吗？
是的 — 「图的表示与遍历准备」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「图的表示与遍历准备」这节课中我会学到什么？
使用邻接表构建有向图和无向图，用 deque 初始化 BFS，用栈或递归实现 DFS，并处理访问记录。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「图的表示与遍历准备」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。