元数据卡
- 前置知识：树（第5章）
- 预计时间：10 分钟
- 完成标志：能理解图的两种表示法和遍历
图是什么
树是一条线（每个节点只有一个父节点）。图打破了这个限制——任何节点都可以连接任何节点。
text
社交网络：人 = 节点，好友关系 = 边
地图：城市 = 节点，道路 = 边
网页：页面 = 节点，超链接 = 边图的表示
python
# 邻接表——最常用
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
# 邻接矩阵——适合稠密图
matrix = [
[0, 1, 1, 0], # A
[1, 0, 0, 1], # B
[1, 0, 0, 1], # C
[0, 1, 1, 0] # D
]| 表示法 | 空间 | 查边 | 遍历邻居 |
|---|---|---|---|
| 邻接表 | O(V+E) | O(degree) | O(degree) |
| 邻接矩阵 | O(V²) | O(1) | O(V) |
DFS 与 BFS
python
# 深度优先（栈/递归）
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 广度优先（队列）
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)| 遍历 | 数据结构 | 特点 | 应用 |
|---|---|---|---|
| DFS | 栈/递归 | 一路走到黑 | 拓扑排序、连通分量 |
| BFS | 队列 | 逐层扩散 | 最短路径、层级遍历 |
旅人笔记
图 = 节点 + 边。邻接表省空间适合稀疏图，邻接矩阵查边快适合稠密图。DFS 深入探索，BFS 逐层扩散。
→ 下一步：图的遍历与搜索
从点到线再到网——用 DFS 和 BFS 解决真实问题。