11.2 游走、路径、环与连通性
第 11.1 节描述了哪些顶点彼此相邻。但网络问题通常不止关心一条局部连接：消息能否从 传到 ？配送路线能否不重复街道？一个中转点故障后会不会把网络切开？
要回答这些问题，需要把相邻的边连接成路线。
游走是限制最少的路线
设 为无向图。从 到 的游走（walk）是有限顶点序列
并且每一对相邻位置上的顶点之间都有边：
游走的长度是经过的边数，也就是 。序列中共有 次顶点出现，因为起点和终点都要记录。
假设
那么
是一条长度为 的游走，依次使用边 。游走允许重复顶点和边，因此它是限制最少的路线概念。
迹、路径、闭游走与环
禁止某些重复，或者要求路线回到起点，就会得到更具体的路线。
迹（trail）是不重复边的游走，但可以重复顶点。
路径（path）是不重复顶点的游走。重复一条边必然重复它的端点，所以每条路径也一定是迹。
起点与终点相同的游走称为闭游走。闭合的迹称为闭迹。
环（cycle）是一种闭迹：起点与终点相同，除此之外的顶点全部不同。在简单无向图中，一个环至少有 条边。
这些定义存在如下包含关系：
反方向一般不成立。例如：
| 顶点序列 | 分类 | 原因 |
|---|---|---|
| 路径 | 没有顶点重复 | |
| 是迹但不是路径 | 重复，但边没有重复 | |
| 是游走但不是迹 | 边 被正反使用了两次 | |
| 环 | 路线闭合，内部顶点各不相同 |
在有向图中必须遵守方向。只有存在弧 时，序列 才是有向游走；不能默认反向弧 也存在。
把游走简化为路径
如果从 到 的游走重复了某个顶点，就观察这个顶点连续两次出现之间的部分。删掉这段闭合绕行后，起点与终点不变，但边数减少了。
反复执行删除，最终会得到不重复顶点的游走，也就是一条路径。因此：
> 如果从 到 存在游走，那么从 到 一定存在路径。
这个事实允许我们使用路径定义连通性，即使最先发现的路线带有绕行。
直接在交通网络上画出路线。动态路线档案会记录重复顶点、重复边、是否闭合以及长度，并判断它是游走、迹、路径、闭迹还是环。你可以主动制造“只差一点”的错误路线，再尝试修复。
顶点连通与图连通
若顶点 与 之间存在路径，就称两者连通。若一张图中任意两个顶点都连通，就称这张图是连通图。
在无向图中，“与……连通”具有第 4 章等价关系的三个性质：
- 每个顶点都通过长度为 的路径与自身连通；
- 若存在从 到 的路径，把顺序反过来就得到从 到 的路径；
- 若路线连接 与 ，另一条路线连接 与 ，把它们接起来就得到从 到 的游走，再删去绕行即可得到路径。
这个等价关系的每个等价类就是图的一个连通分量。连通分量是极大的连通子图：它本身连通，而且不能再加入图中的其他顶点而仍把它当作同一个连通部分。
图 的子图 使用原图的一部分顶点和一部分边，并满足
这里的“极大”不是指“顶点数最大”，而是指这个连通部分无法再向外扩张。不同连通分量的大小可以不同。
桥与割点
第 10 章已经说明树中的每条边都是桥。同一定义也适用于一般图。
删除一条边后，如果连通分量数量增加，就称这条边为桥。环上的边不是桥，因为环中剩余的边仍然为它的两个端点提供备用路线。
删除某个顶点及其所有关联边后，如果连通分量数量增加，就称这个顶点为割点。
边故障与顶点故障并不相同。考虑边集
三角形 与 都能为各自的边提供备用路线。边 是桥。顶点 连接两个三角形，所以是割点；顶点 是 唯一的连接入口，因此也是割点。
删除一个孤立顶点不会让其余顶点形成更多连通分量，所以按照这个定义，孤立顶点不是割点。
用系统探索寻找连通分量
寻找起点 所在的连通分量，可以这样做：
1. 把 标记为已到达；
2. 反复检查从已到达顶点出发的边；
3. 把新遇到的邻居标记为已到达；
4. 当所有边都无法通向未到达邻居时停止。
此时，已到达集合恰好就是 所在的连通分量。若图中还有未到达顶点，就从其中任选一个重新探索，以找到下一个分量。第 11.3 节会把这个思路发展为广度优先搜索和深度优先搜索算法。
在故障演练中操作通信网络：移除一条链路或一个中继站，实时观察连通分量如何分裂，找出桥与割点，并尝试用最少的修复恢复冗余。
从“存在路线”走向搜索算法
游走、迹、路径与环的区别在于允许哪些重复。连通性只询问某条路径是否存在，桥和割点则暴露单点故障。
上面的探索过程已经说明“要做什么”，但还没有规定“按什么顺序做”。第 11.3 节会明确探索顺序：不同的前沿规则产生广度优先搜索和深度优先搜索，加入边权后则会引出最短路径算法。