动机
多种图算法都反复选取顶点或边,但证明保护的意义不同。广度优先搜索确定按边数计的距离;最小生成树最小化连接所有顶点的总成本;Dijkstra 算法确定从源点出发的距离。混淆这些目标,可能得到看似合理、实际却解了另一问题的算法。
本篇使用有限简单图,顶点集 、边集 ,以邻接表表示。有向边为有序对,无向边在两端各检查一次。路径不重复顶点,游走则容许重复。加权结论假设精确实数加法及比较为单位成本;长整数或有限精度须另作分析。记 。
定义
定义 3.2.1
(遍历与距离)
若从源点 存在遵从方向的有向路径到某顶点,便称该顶点可达。无向边可向任一方向走。无权距离是这种路径的最少边数,不可达者为无穷。加权距离取源点到该顶点的全部游走权重之下确界;无游走时为正无穷,权重无下界时为负无穷。可达负环可能使相关可达顶点的距离成为负无穷。
定义 3.2.2
(树、割与松弛)
连通无向图的生成树是包含全部顶点、连通且无环的子图。最小生成树(MST)在所有生成树中总边权最小。割把顶点分成一个非空子集与其非空补集;端点分处两边的边称为跨割边。松弛有向边 ,指把暂定距离 改为 ;若 无穷则忽略。
连通无环图中每对顶点有唯一路径,因为两条不同路径会形成环。删去树边会使它断开;加入新边则恰产生由该边及原有唯一路径构成的一个环。这些基本事实支持后面的交换证明。权重相同时 MST 未必唯一,且 MST 问题容许负权。
定理 / 命题
定理 3.2.3
(遍历保证)
广度优先搜索(BFS)在首次入队时标记顶点,使用先进先出队列。源点距离为零,初次发现邻点时设其距离为当前顶点距离加一。所得距离是真正无权最短距离,并在 时间找出全部可达顶点。
深度优先搜索(DFS)在完成当前顶点前,先递归探索每个未访邻点。完整 DFS 森林需 时间。有向无环图中,把完成次序倒转便得拓扑排序,即每条边均指向次序较后者。
定理 3.2.4
(割交换与 Kruskal 算法)
若森林 包含于某 MST,且某割没有 中的跨割边,则跨割的最轻边可加入 ,同时仍包含于某 MST。因此 Kruskal 算法按非递减权重扫描边,只在两端属不同当前分量时接受,会在连通无向图构造 MST。
定理 3.2.5
(Dijkstra 的确定规则)
若全部边权非负,初始化 、其余无穷;每次确定未处理顶点中有限暂定距离最小者,并松弛其出边。每个确定值都是真正最短距离。当再无有限未确定值,其余顶点均不可达。
定理 3.2.6
(含负边的 Bellman–Ford 算法)
设从 不可达任何负环。则在对每条边松弛的 轮之后,标号等于真实距离,所需时间为 。再多做一轮后仍能降低某个标号,当且仅当从 可达一个负环。
证明思路或证明
证明
(BFS 依距离次序发现顶点)
BFS 记录实际路径:新顶点的路径是在当前路径后接一边。队列按非递减距离处理顶点。最初只有距离零;处理距离 顶点时,只会在现有队列后加入距离 者,而原队列的距离为 或 ,归纳得次序性。若某顶点初次距离大于真正最短值,在一条最短路径上取首个未得到正确距离的顶点。其前驱已有正确的较小距离,会在任何能给出较长发现路径的顶点前处理,从而以正确距离发现该点,矛盾。可达性亦由路径上首个未发现顶点证明:其已发现前驱终会检查相应边。
入队时标记保证每顶点至多入队一次,每个邻接项检查一次,加上初始化即得所述时间,包括非连通输入。前驱指针可重建最短路径,在可达顶点上形成发现树。对加权图使用 BFS 仍只最小化边数,未必最小化总权重。
DFS 完成时间证明什么
证明
(反向完成次序是拓扑排序)
使用三色:发现前白色,递归栈中灰色,完成后黑色。有向边指向灰色邻点时,该邻点是活跃栈中的祖先,栈路径加这条边便构成有向环。有向无环图不可能出现这情况。考虑边 :检查时若 白色,它将递归完成后才完成 ;若黑色,它已完成;灰色不可能。因此每条边的 都比 早完成,倒转完成次序便拓扑有序。
对每个剩余白色顶点再启动 DFS,可覆盖非连通图与全部有向分量。每顶点只经一次各色转换,每个邻接项只检查一次,所以线性。无向图检测环须另外处理回到父点的边,不能不加条件复制有向灰边判据。
反例模式
无向图中的灰色邻点
考虑这样的说法:在无向图中,DFS 遇到灰色邻点就证明存在环。取只有一条边 的图,从 开始 DFS。它发现 ,而从 考察通向 的边时, 是灰色的。所谓的环是 ,但这个图根本没有环。回到父顶点的边就是同一条无向边,不是第二条边。对简单无向图,修正后的判据要忽略指向父顶点的树边:不是父顶点的灰色邻点,经由另一条边到达,才说明存在环。
MST 的交换
证明
(最轻的跨割边是安全的)
取包含 的 MST , 为跨割最轻边。若 ,已完成;否则把 加入 产生唯一环。原来连接两端的路径也跨过此割,所以环含另一跨割边 。由 无跨割边,。删 恢复生成树并包含 。由 ,新树权重不大于最优的 ,故亦最优。平手时也成立。
证明透视
被换出的边为何存在而且无害
交换是一次只换一条边的操作,依赖两个关于割的事实。把 加入树中会形成一个经过 的环,而与割只相交一次的环必定再次穿过该割,所以边 存在。由于 中没有边跨越这个割,,所以删去 之后,新树仍包含 。不等式 是用到“最轻”的唯一之处,它使新树不会更重。若去掉对 的条件,就可能 ,交换会破坏包含关系;若去掉最轻的条件,就可能 ,树可能变重。只需要 ,所以权重相同并无妨碍。
证明
(Kruskal 算法构造 MST)
Kruskal 起初空森林包含于某 MST。对每条接受边,取其某端的当前分量形成割;已接受边均不跨割。此边跨割最轻,因为更轻跨割边早已处理,而且其两端现在仍不同分量,当时也必不同,应已被接受。因此安全边命题保持不变量。每次接受都合并分量而不产生环。若扫完仍有多个分量,连通性会给出一条应被接受的分量间边,矛盾。最后森林遂连通且为 MST。
实现分量时,无需假设复杂摊销定理:用父指针树,把较小分量的根接到较大分量根之下。每当某顶点深度增加,其分量大小至少加倍,故深度至多 。每条边的找根与合并需 。排序需 ;简单图有 ,故总时间 ,空间 。路径压缩改进不在此证明内。
Dijkstra 为何需要非负边
证明
(Dijkstra 确定的是真实距离)
每个有限暂定距离都是某实际源点游走的权重,所以在最优值存在时不小于它。非负权允许移除环而不增加成本,因此每个可达顶点都有最短路径。假设先前确定均正确,取下一选定顶点 。在到 的最短路径上,取首个未确定顶点 。若 ,暂定值为零;否则其前驱 已确定,松弛 已令 不大于到 的最短路径前缀权重。最短路径前缀也最优,否则替换较好前缀会改善整条游走,再删环即可改善路径。
非负性保证此前缀权重不大于到 的完整距离。最小选取规则给 ;实际游走性质给反向不等式,故确定正确。若尚有可达顶点而所有未确定值均无穷,取可达路径上首个未确定点,其已确定前驱应给它有限值,矛盾。
证明透视
路径上第一个未确定的顶点
证明不能直接把 与它在最短路径上的前驱相比,因为那个前驱本身可能尚未确定。关键的一步是选取 ,即路径上第一个未确定的顶点。它的前驱已确定,所以松弛已经使 不超过该路径前缀的权重。非负性只使用一次:说明这个前缀不会比整条路径更重,得到 。若 之后有负边,整条路径可能比前缀更轻,这个不等式就不成立。对 的最小选取给出 ,而“每个有限标号都是实际游走的权重”给出 。
每次扫描未确定顶点找最小,时间为 ,邻接表以外距离及前驱空间为 。二元堆可改善界,但须另证操作成本;距离不变量的正确性不依赖优先队列实现。距离与前驱也不同:零权平手时应有一致更新规则,避免相同值替换造成前驱环。
负边与 Bellman–Ford
证明
(Bellman–Ford 求出距离并检测负环)
负边破坏 Dijkstra 的前缀不等式,但可改为限制游走边数。令 为最多用 边到 的最小游走权重,,其余初值无穷。则
方案已穷尽:游走或最多用 边,或有最后一边且前缀最多用 边。反之,每个有限候选值都能接边实现。若无从 可达的负环,删去环不增加成本,最优路径最多用 边,故 给出全部距离。
通常原地 Bellman–Ford 初始化后,作 轮,每轮松弛所有边。第 轮后的值不大于 ,因为每轮内值只减少,可用归纳证明;它们仍是实际游走权重。因此没有可达负环时, 轮后恰等于真正距离。时间 ,辅助空间 。直接用两行计算上述式子也正确,但每轮复制全部顶点时时间为 ;其中间行未必等于原地算法的中间值。
若额外一轮仍可减少有限距离,便检测到可达负环。若无此环,距离已精确,不可能再降。反之,若无边可下降,沿可达环把 相加,便得环权重非负;可达性传播后其全部顶点标号都有限。因此可达负环必迫使某个进一步下降。单源初始化不检测不可达负环,而它们也不影响该源点的距离。
例题详解
例题 3.2.7
(有向图的 BFS 层)
边为 。BFS 层为 ,距离依次零、一、二、三。视邻接次序而定, 或 都可能成为 的前驱。距离唯一,选出的最短路径却未必唯一。
例题 3.2.8
(生成树不是最短路径树)
无向三角形取 。MST 用 ,总重四,其树上 到 路径重四,但图中最短路线是重三的 。以 为根的最短路径树用 ,总重五。两棵树各自优化其指定目标。
反例模式
没有负环并不足以使用 Dijkstra
考虑这样的说法:只要图中没有负环,Dijkstra 的确定规则就仍然正确。取有向边 权重为二, 权重为五, 权重为负四。Dijkstra 在考察 之前就以 确定 ,因为 。路径 的权重为 ,所以到 的真实距离是一。这个图完全没有环。该规则需要每条边的权重各自非负;而不提前确定任何顶点的 Bellman–Ford 算法会得到值一。
例题 3.2.9
(含不可达顶点的 Dijkstra)
设有向边为 权重 , 权重 , 权重 ,且 没有入边。起初 ,其余标号为无穷。确定 并松弛,得 、。确定最小有限标号的 ,并松弛 ,得 。确定标号为 的 之后,只剩下标号为无穷的 ,规则于是停止。各距离为 。通向 的直接边并不是最短的,而不可达的顶点 保持 。
概念视角结构
三种选择,三种保证
BFS 选队首顶点,确立边数层;Kruskal 选边,确立仍可延伸到全局最优生成树;Dijkstra 选最小标号,确立该标号不会再改善。选取形式相似,但保证及假设不同;MST 交换不能替代最短路径确定证明。
常见错误
常见错误
(先确认问题,再选算法)
先确认图是否有向、关心全部顶点还是单源、权重可否为负。非连通无向图没有生成树,Kruskal 只产生各分量的最小生成森林。DFS 树路径一般非最短。向部分森林加边安全,是因为割证明,不能只因边便宜。
常见错误
(表示方式与哨兵值)
复杂度依赖表示及数据结构。邻接矩阵需二次空间,与稀疏邻接表不同。最短路径还须区分无穷与很大的有限数;数学证明未保证某个可能溢出或与真正距离混淆的哨兵值安全。
总结
遍历不变量建立可达性、层及完成时间次序。MST 的割交换保持可延伸至最优解。Dijkstra 靠非负权确定最小标号,Bellman–Ford 则用反复松弛及明确负环检测。指出各自保护的保证,可分清及检验外表相近的图程序。
练习
快速检查
(给有向图,使 DFS 因邻接次序而首次找到比最短路径长的路径。)
让 既有指向目标的直接边,又有一条较长的路线。
解答 · 答案
用边 ,并从 先探索 再探索 。DFS 首次沿三条边到达 ,而直接边的长度为一。这条发现路径有效,但并非最短。
快速检查
(解释为何用任意非最轻跨割边取代最轻边会破坏 MST 证明,并给加权三角形例。)
交换用到哪一个不等式?
解答 · 答案
交换需要 ,这样交换才不会增加树的权重。取三角形,,,,并取割 对 。边 跨越该割但不是最轻的,因为 也跨越该割且权重为一。每棵含 的生成树还含 或 ,所以权重至少为 ,而最小生成树 的权重为三。因此 不是安全边。
快速检查
(边 权四、 权五、 权负二。计算 及真正距离。)
每一行都按 的次序书写。
解答 · 答案
按 次序,,,,因为 。图中没有环,最后一行就是真正距离。若原地的一轮先考察 再考察 ,第一轮就可能得到二,这说明它的中间数组不必等于同步的各行。
练习 3.2.10
(证明有限有向图有拓扑排序,当且仅当它没有有向环。)
核心证明
可使用上面证明过的 DFS 三色论证。
解答(3)
- 1
排序排除有环
沿着一个有向环,相邻顶点的位置会严格递增并回到起点,这是不可能的。
依据: 在拓扑排序中,每条边都严格增加位置。
- 2
无环排除灰色邻点
关键一步
若在无环图上,DFS 从 遇到灰色邻点 ,则栈上从 到 的路径加上边 就是一个有向环。
依据: 灰色邻点会与栈上的路径构成环。
- 3
反向完成次序是拓扑排序
∎对 DFS 考察的边 , 若是白色,就会先于 完成;若 已是黑色,则早已完成。所以 先于 完成,于是在反向完成次序中 排在 之前。每条边都如此,所以这个次序是拓扑排序。