7.1 图的模型与遍历：先定义边，再选择表示
服务调用、网页链接和用户关注都能画成点与箭头，但三者的“边”语义不同：一次调用还是可能调用，静态依赖还是运行时观测，能否自环，重复边是否有意义。图算法之前要先定义模型。
图的基本结构
图写作：
G=(V,E)V：顶点集合；E：边集合。
无向简单图的边可视为含两个不同顶点的无序集合 {u,v}；有向图的边是有序对 (u,v)，写作 u→v。
还要声明：
- 是否允许自环
(v,v)； - 同一对顶点间是否允许多条平行边；
- 边是否带权、容量、标签或时间；
- 图是静态快照还是会更新。
允许平行边的图称为多重图。航班网络中同两座城市间多趟航班可能要保留为不同边；“是否互相关注”的模型则通常只需要简单图。
若保留平行边，单纯的端点集合会丢失重复次数；可给每条边独立 ID，或用允许重复的边记录序列。度数与容量应按选定的边身份计算。
度与握手定理
无向图中顶点 v 的度 deg(v) 是与它关联的边数，自环按通常约定贡献 2。
Σ_{v∈V} deg(v)=2|E|每条边有两个端点，所以在度数总和中被数两次。这立刻推出：奇数度顶点的数量一定是偶数。
有向图区分入度、出度：
Σ indeg(v)=Σ outdeg(v)=|E|构建拓扑排序时会使用入度；分析热点依赖时，出度和入度代表不同含义。
三种常见存储
设 n=|V|, m=|E|。
邻接表
为每个顶点保存出邻居：
A: [B,C]
B: [D]
C: [D]
D: []空间通常为 Θ(n+m)，遍历所有邻居高效，适合稀疏图。查询指定边是否存在的成本取决于邻居容器是数组、集合还是排序结构。
邻接矩阵
M[u,v]=1 ⇔ (u,v)∈E空间 Θ(n²)，边存在查询常数时间，适合顶点较少或图较稠密的场景。带权图可存权重和“无边”哨兵，但必须区分权重 0 与不存在。
边列表
直接保存：
(u,v,w)适合按边排序、批处理和 Kruskal 算法；从某顶点找邻居则不方便，除非另建索引。
没有一种表示对所有操作最优。模型规模、查询模式、更新频率和内存布局共同决定选择。
BFS：按边数分层扩展
广度优先搜索从源点逐层访问：
BFS(G,s):
queue=[s]
discovered={s}
distance[s]=0
while queue 非空:
v=queue.pop_front()
for u in neighbors(v):
if u 不在 discovered:
discovered.add(u)
distance[u]=distance[v]+1
parent[u]=v
queue.push_back(u)应在发现并入队时标记节点，而不是出队时才标记，否则同一节点可能被多个前驱重复入队。
在无权图或所有边权相同的图中，BFS 第一次发现顶点时得到从源点出发的最少边数距离。它不保证普通带权图的最小权重路径。
parent 可重建路径：从目标沿父指针回到源点再反转。若只记录距离而不记录父节点，无法直接输出具体路径。
下面的 Python 3 示例用 deque 保证队首弹出为常数时间。图是有限静态邻接表，所有邻居也有键，源点存在；顶点使用字符串，None 留作父指针终止标记：
from collections import deque
def bfs(graph, source):
distance, parent = {source: 0}, {source: None}
queue = deque([source])
while queue:
v = queue.popleft()
for u in graph[v]:
if u not in distance:
distance[u], parent[u] = distance[v] + 1, v
queue.append(u)
return distance, parent
def path_to(parent, target):
if target not in parent:
return None
path = []
while target is not None:
path.append(target)
target = parent[target]
return path[::-1]
graph = {"A": ["B", "C"], "B": ["D"], "C": ["C", "D"],
"D": ["A"], "E": []}
distance, parent = bfs(graph, "A")
print(distance["D"], path_to(parent, "D")) # 2 ['A', 'B', 'D']
print(path_to(parent, "E")) # NoneD 有两个前驱，仍只会入队一次；自环和返回 A 的环也不会反复访问。若交换 A 的邻居顺序，可得到另一条同样短的路径，经 C 到 D；距离保证与路径唯一性是两回事。
DFS：沿一条分支深入
深度优先搜索可以递归，也可用显式栈：
DFS(v):
discovered.add(v)
for u in neighbors(v):
if u 不在 discovered:
parent[u]=v
DFS(u)正确维护 discovered 后，有环图不会无限递归。若递归深度可能很大，显式栈可避免语言调用栈溢出，但仍要保存 visited。
DFS 的进入、退出时间可用于：
- 检测有向图回边；
- 生成 DFS 森林；
- 拓扑排序；
- 强连通分量算法；
- 桥和割点分析。
这些结论依赖更细的颜色或时间状态，仅有一个最终 visited 集合不总能区分“正在当前递归栈中”和“已经完成”。
不连通图需要逐个遍历连通分量
从单个源点运行 BFS/DFS，只覆盖它可达的顶点。要访问整张图：
for v in V:
if v 未访问:
从 v 开始一次遍历每次新启动产生一棵搜索树，合起来是搜索森林。无向图中启动次数等于连通分量数。
时间复杂度来自表示
对整张图的遍历，或源点能到达所有顶点时，邻接表上的 BFS/DFS 为：
Θ(|V|+|E|)因为每个顶点处理一次，每条边检查常数次。无向图在邻接表中一条边通常出现两次，但只改变常数。
单源遍历若只到达部分图，则工作量是 Θ(|V_s|+|E_s|)，其中 E_s 是从可达顶点出发的邻接条目；初始化全图数组还可能额外花 Θ(|V|)。上述界假设顶点索引、集合查询和队列操作具有单位成本。
邻接矩阵上，即使图很稀疏，也要为每个访问顶点扫描整行，全图遍历通常是 Θ(|V|²)。
复杂度结论必须注明图表示。只写“DFS 是 O(V+E)”默认了能按实际邻边枚举。
图模型里的身份和重复
现实数据导图时要决定：
- 用户重命名后是否仍是同一顶点；
- 两条重复日志是否是一条边还是两次事件；
- 时间窗口外的边是否删除；
- 聚合边权是次数、延迟总和还是平均值；
- 方向是“调用”还是“被调用”。
算法对数学图正确，不代表抽取出的图表达了业务问题。
完成检查
- 为包依赖、道路和消息投递分别定义顶点、边、方向与权重；
- 比较邻接表、矩阵和边列表的内存及查询；
- 手工执行一次 BFS，写出 distance 与 parent；
- 手工执行一次 DFS，标出进入/退出顺序；
- 构造一个有环图，说明 visited 为何阻止无限遍历；
- 构造不连通图并得到搜索森林。