82-Graph-Exercise

6-1 关联矩阵

说明：关联矩阵 Incidence Matrix ：对于含有 n 个顶点、e 条边的图，对应关联矩阵 I[][] 共有 n 行 e 列。在无向图中，对于任意的 0 ⇐ i < n 和 0 ⇐ j < e，若第 i 个顶点与第 j 条边彼此关联，则定义 I[i][j] = 1；否则，定义 I[i][j] = 0。

关联矩阵与邻接矩阵有何关系？就无向图而言（不考虑自环等情况），既然每一条边均恰好与两个顶点关联，故该关联矩阵中的每一列都应恰好包含两个1，总和均为2。

考查关联矩阵与其转置的乘积 $B = I \cdot I^{T}$ 。

该矩阵对角线上的任意元素 B[i][i]，都应满足： $B [i] [i] = I [i] \cdot I [i]^{T}$ = 顶点 i 的度数，
而对于对角线以外的任意元素 B[i][j]，i != j，都有 $B [i] [j] = I [i] \cdot I [j]^{T}$ = 顶点 i 与顶点 j 之间公共的关联边数。

也就是说，B[i][j] 等于1/0当且仅当顶点 i 与顶点 j 是/否彼此邻接。

有向图的关联矩阵如何定义？通常的定义方式为，对于任意的0 ⇐ i < n 和0 ⇐ j < e，若第 j 条边从第 i 个顶点发出（即顶点 i 为边 j 之尾），则定义 I[i][j] = -1；若第 j 条边进入第 i 个顶点（即顶点 i 为边 j 之头），则定义 I[i][j] = +1；否则，定义 I[i][j] = 0。
有向图的关联矩阵与其邻接矩阵又有何联系？与无向图类似地，有向图关联矩阵中的每一列应包含+1和-1各一个，总和应均为0。为发现此时两种矩阵之间的联系，不妨依然考查关联矩阵与其转置的乘积 $B = I \cdot I^{T}$ 。

对于该矩阵对角线上的任意元素 B[i][i]，都有 $B [i] [i] = I [i] \cdot I [i]^{T}$ = 顶点 i 的（出、入总）度数，
而对于对角线以外的任意元素 B[i][j]，i != j，都有 $- B [i] [j] = - I [i] \cdot I [j]^{T}$ = 顶点 i 与顶点 j 之间公共的关联（有向）边数。

也就是说，B[i][j] 等于0当且仅当顶点 i 与顶点 j 互不邻接；B[i][j] 等于-1或-2，当且仅当在顶点 i 与顶点 j 之间，联接有1或2条有向边。

6-2 邻接矩阵 insert 操作的分摊复杂度

首先请注意，GraphMatrix 类（教材157页代码6.2）在底层，是基于可扩充向量，以二维 Vector 结构的形式来实现邻接矩阵。

按照第2.4节的实现方法及其分析结论，每一向量（即邻接矩阵的每一行）的单次插入操作，在分摊意义上只需 O(1) 时间。这里，在每一节点的插入过程中，n 个向量的操作（含扩容操作）完全同步，故总体的运行时间不超过分摊的 O(n)。

当然，为插入一个顶点，在最坏情况下可能需要访问和修改整个邻接矩阵，共需 O(n^2）时间。

6-3 平面图的边数量

描述：平面图指 n 个顶点映射在同一平面上，且顶点之间所有的联边只相交于公共断点，而不是边的内部。==证明平面图必定满足 e=O (n)==，即边数和顶点数同阶。 (提示：平面图必然遵守欧拉公式 n-e+f-c=1，其中 n, e, f, c 分别为平面图的顶点、边、面、连通域的数目)

不妨设这里所讨论的平面图，如图 x6.1(a)所示，至少包含3个顶点；自然地，同时也包含 c >= 1个连通域。考查其中各边与各面之间的关联关系，将面的总数记作 I。

首先不难看出，悬边仅与一张面关联，其余各条边均与两张面相关联。因此，每条边对 I 的贡献至多为2，故有： I ⇐ 2e… (1)

另一方面，平面图中仅有一张无界的面——即所谓的外面（outer face）——它对 I 的贡献至少为3。此外其余的各张面，均由至少三条边围成，对 I 的贡献也至少为3，故有： 3f ⇐ I… (2)

联立不等式(1)和(2)，即有： 3f ⇐ 2e, f ⇐ 2e/3… (3)

将不等式(3)代入欧拉公式，则有： 1 = n - e + f - c ⇐ n - e + 2e/3 - 1 稍作整理，即得： e ⇐ 3n - 6 = O(n) … (4)

并且，(4)取等号，当且仅当 (1~3)取等号。此时，每张面（包括外面）应恰好由三条边围成。也就是说，该平面图不仅如图 x6.1(b) 所示，是习题6-32 中定义的三角剖分（triangulation），而且更如图 x6.1(c)所示，外面也必须是一个三角形。

6-4 无向图二维邻接矩阵映射至一维向量

无向图的邻接矩阵必然对称，亦即，A[i][j] = A[j][i] 对合法的任意 i 和 j 均成立。因此，邻接矩阵的上或下半角完全可以不必记录，并将剩余部分转化并压缩为一维向量 A’。

这里，不妨仅保存其中的下半三角区域（含对角线），即所有满足0 ⇐ j ⇐ i < n 的元素 A[i][j]。于是如图 x6.2所示不难验证，可以在这些元素与向量 A’之间建立如下一一对应关系： $A [i] [j] \Leftrightarrow A^{'} [i (i + 1) /2 + j]$ 或者等价地： $A^{'} [k] \Leftrightarrow A [i] [k - i (i + 1) /2]$ ，其中 $i = ⌊(8 k + 1 - 1) /2 ⌋$ 如此所得一维向量 A’的长度为 n(n + 1)/2，大致为未压缩之前的一半。但就渐进意义而言，空间复杂度依然为 O(n^2)。

另外，就从 A 中元素到 A’中元素的映射而言，以上转换均属于基本操作，各自仅需 O(1)时间。

但是仍然会影响接口的效率：既然以上转换均属于基本操作，故在顶点集保持不变的情况下，各接口所需时间将保持不变。然而在图的规模可能发生改变的场合，无论是新顶点的引入还是原顶点的删除，都有可能需要移动A’中的所有元素，从而造成巨大的额外时间开销，因此得不偿失。

6-5 邻接表实现图的各类操作接口

//邻接矩阵框架
#include "../Vector/Vector.h" //引入向量
/* ... */
template <typename Tv, typename Te> //顶点类型、边类型
class GraphMatrix : public Graph<Tv, Te> { //基于向量，以邻接矩阵形式实现的图
private:
 Vector< Vertex< Tv > > V; //顶点集（向量）
 Vector< Vector< Edge< Te >* > > E; //边集（邻接矩阵）
 /* ... */
}

//邻接表框架
#include "../Vector/Vector.h" //引入向量
#include "../List/List.h" //引入列表
/* ... */
template <typename Tv, typename Te> //顶点类型、边类型
class GraphList : public Graph<Tv, Te> { //基于向量和列表，以邻接表形式实现的图
private:
 Vector< Vertex< Tv > > V; //顶点集（向量）
 Vector< List< Edge< Te >* > > E; //边集（邻接表）
 /* ... */
}

可见，所有顶点依然构成一个向量，且分别将各自的关联边组织为一个列表（即所谓边表）。既然同一边表内的边都关联于同一顶点，故为了便于查找另一关联顶点，接下来还需相应地在原 Edge 边结构的基础上，再增加一个域 v：

template <typename Te> struct Edge { //边对象
 Te data; int weight; EStatus status; //数据、权重、状态
 int v; //关联顶点
 Edge( Te const& d, int w ) : data( d ), weight( w ), status( UNDETERMINED ) {} //构造新边
};

对于有向图，可以统一约定各边分别归属于其尾顶点所对应的边表（出边表），或统一归属于其头顶点（入边表）。而为了提高查找效率，甚至可以同时为各顶点设置出边表和入边表。 Graph 各标准接口的具体实现，也要做相应的调整，凡涉及边表的操作都要将此前 Vector 结构的操作替换为 List 结构的操作。

分析邻接表的时间、空间效率。邻接表的时间复杂度在空间复杂度方面，邻接表可以动态地与图结构的实际规模相匹配，而不再是固定的Θ(n^2 )。具体地，若当时的图结构共含 n 个顶点、e 条边，则实际的空间消耗应不超过 O(n + e)。

与邻接矩阵相比，多数针对顶点的操作的时间复杂度几乎不变，但涉及边的操作则不尽相同。在这里，边确认操作 exists(i, j) 的作用至关重要。

改为邻接表之后，我们需要遍历顶点 i 所对应的边表，方可判定其中是否存在与顶点 j 相关联者，因此其所需时间由 O (1)增加至 O (deg (i)) = O (n)。
相应地，涉及 exists ()操作的顶点删除操作 remove (i)也需要更多的时间。
此外，在改用邻接表之后，边删除操作 remove(i, j)也需要以类似的方式确认边(i, j)的确存在，并在存在时确定该边记录的存放位置，因此该操作也将不能在 O(1)时间内完成。

6-6 BFS 设计 O (n+e)分解无向图为极大连通域

实现

//广度优先搜索BFS算法（单个连通域）
template <typename Tv, typename Te> 
void Graph<Tv, Te>::BFS( Rank v, Rank& dClock ) { // v < n
	Queue<Rank> Q;
	status( v ) = DISCOVERED; 
	Q.enqueue( v ); 
	dTime( v ) = dClock++; //起点入队
	
	for ( Rank fClock = 0; !Q.empty(); ) { //在Q变空之前，反复地
	    if ( dTime( v ) < dTime( Q.front() ) ) //dTime的增加，意味着开启新的一代，因此
	        dClock++, fClock = 0; //dTime递增，fTime复位
	    v = Q.dequeue(); //取出首顶点v，并
	    for ( Rank u = firstNbr( v ); -1 != u; u = nextNbr( v, u ) ) //考查v的每一个邻居u，视u的状态分别处理
	        if ( UNDISCOVERED == status( u ) ) { //若u尚未被发现，则发现之
		        status( u ) = DISCOVERED;//对该顶点作发现操作
		        Q.enqueue( u ); 
		        dTime( u ) = dClock;
		        
	            type( v, u ) = TREE;//引入树边，拓展BFS树
	            parent( u ) = v; 
	    } else //若u已被发现，或者甚至已访问完毕，则
	        type( v, u ) = CROSS; //将(v, u)归类于跨边
	    
	    status( v ) = VISITED; 
	    fTime( v ) = fClock++; //至此，v访问完毕
	} //for
} //BFS

指向原始笔记的链接

推广：全图BFS

连通分量：在给定无向图中，找出其中任一顶点 s 所在的连通图； 可达分量：在给定有向图中，找出源自其中任一顶点 s 的可到达分量；

实现思路：从 s 出发作 BFS，输出所有被发现的顶点，队列空后立即中止，无需考虑其它顶点。

若图中包含多个连通/可达分量，如何对全图进行 BFS？
template <typename Tv, typename Te> //广度优先搜索BFS算法（全图）
void Graph<Tv, Te>::bfs( Rank s ) { // s < n
	reset(); Rank dClock = 0; //全图复位
	for ( Rank v = s; v < s + n; v++ ) //从s起顺次检查所有顶点
	    if ( UNDISCOVERED == status( v % n ) ) //一旦遇到尚未发现者
	        BFS( v % n, dClock ); //即从它出发启动一次BFS
} //如此可完整覆盖全图，且总体复杂度依然保持为O(n+e)
复杂度（考查无向图）：

bfs ()初始化的 reset ()：O (n+e)

BFS ()的迭代：

外循环（while (!Q.empty)）每个顶点各进入 1 次，

内循环（枚举 v 的每个邻居）：O (1+deg (v)) //邻接表

故总共 $O (v \in V \sum (1 + d e g (v))) = O (n + 2 e)$

整个算法：O (n+e)+O (n+2e)=O (n+e)

有向图亦是如此！

指向原始笔记的链接

子算法 BFS(v)只有在访遍顶点 v 所属的极大连通域之后，方可返回；此后，若还有其它尚未访问的连通域，则算法主入口 bfs()中的循环必然会继续检查其余的所有顶点，而一旦发现尚处于 UNDISCOVERED 状态的顶点，即会再次调用子算法 BFS()并遍历该顶点所属的极大连通域。

由此可见，只需按照 BFS()的各次调用顺序，分批输出所访问的顶点以及边，即可实现无向图的极大连通域分解。

相对于基本的广度遍历算法，除了顶点和边的输出，该算法并未引入更多操作，因此其时间复杂度依然是 O(n + e)。

并且 DFS 同样可以用于连通性的检测。

6-7 BFS 辅助队列的特性

说明：以 $π (s, v)$ 记作 s 到 v 的最小距离。

证明：BFS 过程中，波峰集中的各顶点始终按在 BFS 树中的深度，在辅助队列中单调排列，且彼此相差不超过 1。采用数学归纳法，证明该不变性在每一顶点入队后都成立。初始时队列为空，自然成立。考查下一入队顶点 u，其在 BFS 树中的深度 depth(u)，是在其入队的同时确定的。就在 u 入队的那一步迭代中，此前必有某一顶点 v 刚刚出队，且在 BFS 树中 u 是 v 的孩子，故有： depth(u) = depth(v) + 1 因此，倘若题中所述不变性在该步迭代之前成立，则在 v 出队、u 入队后应该继续成立。
最短路径
- 无向图中，将顶点 v 到 u 的距离记作 dist (v, u)，在 v 的视角里，简记作 dist(u)，下面的描述就是这个意思
- BFS 过程中，队列 Q 的变化如下：
  - 队列中的顶点按照 dist (s)单调非递减（非递增当然也可以）排列
  - 相邻顶点的 dist (s)相差不超过 1
  - 首、末顶点的 dist (s)相差不超过 1 （意思是队列中始终保持在相邻的层次内遍历）
  - 由树边连接的顶点，dist (s)恰好差 1 ⭐
  - 由跨边连接的顶点，dist (s)至多相差 1 ⭐
- BFS-Tree 中从 s 到达 v 的路径，即是二者在原图中最短的通路
指向原始笔记的链接
证明：所有顶点按在 BFS 树中的深度，非降次序接受访问。根据以上分析，BFS 树是在广度优先搜索的过程中自上而下逐层生成的，各顶点也是以其在树中的深度为序逐个被发现的；反过来，对原图的广度优先搜索过程，完全等同于对 BFS 树的层次遍历过程。 原图的各边所联接的顶点，在 BFS 中的深度之差不超过1；由树边联接的顶点，在 BFS 树中的深度之差恰好为1。
证明：所有顶点按其到 s 的距离，以非降次序接受访问。由上，只需证明每一顶点 u 都满足 $π (u) = d e pt h (u)$ 。反证，假设至少有一个顶点不满足这一性质。以下，考查此类顶点中 $π ()$ 值最小者 u。

既然在 BFS 树（原图的子图）中已有一条长度为 depth(u)的通路联接于 s 和 u 之间，故必有： $π (u) \leq d e pt h (u)$ 因此，不妨假定： $π (u) < d e pt h (u) ................................................ (1)$

在原图中，考查 s 到 u 的（任何一条）最短路径，其长度即为 $π (u)$ 。显然 u != s，故 u 在该通路上的直接前驱顶点存在。将次前驱顶点记作 v，则 v 应满足： $π (v) = π (u) - 1 < π (u) .................. (2)$

根据 u 之 $π ()$ 值的最小性，这就意味着 v 必然满足： $π (v) = d e pt h (v) ................................................ (3)$

综合(1)、(2)和(3)，即得： depth(v) + 1 < depth(u) 然而，这一不等式不可能成立。实际上，在顶点 v 出队时，作为 v 的邻接顶点之一，u 必然会在同一步迭代中入队，并且同时确定其在 BFS 树中的深度为： depth(u) = depth(v) + 1 需要强调的是，以上分析过程及结论，对于有向图同样适用。

6-8 BFS 在 O (n+e)计算起始点到其余顶点的最小距离

背景：无向图中，且所有边权值相同。计算出起始点到其余顶点的最小距离和最短通路。

经过广度优先搜索之后，各顶点在 BFS 树中的深度值，即是在原图中从起始顶点到它们的（最小）距离。因此，只需套用该算法，在每个顶点入队时随即输出其所确定的深度值；而在最终生成的 BFS 树中，从树根到各顶点的（唯一）通路，即是对应的（最短）通路。

需要强调的是，在原图中，任意两个顶点之间的（最短）通路可能不止一条，但它们的长度必然相同。

6-9 BFS 在 O (n+e)内找到直径（无向图中最长通路）

算法的主体流程如下：

首先从任一顶点 v 出发，经过一趟广度优先搜索，找到与之距离最远的顶点 a；
然后从 a 出发，再经过一趟广度优先搜索，找到与之距离最远的顶点 b。

不难证明，在后一棵 BFS 树中，ab 之间的通路即是原图的直径。

当然，按照题中所给定义，同一无向连通图的直径可能不止一条。有兴趣的读者不妨进一步拓展以上算法，从任一无向连通图中找出所有的直径。

6-10 DFS 在 O (n+e)内判断是否存在欧拉环路并构造之

根据图论的基本结论，只需遍历全图确定其连通性，再核对各顶点的度数。若连通且没有奇度数的顶点，则必然存在欧拉环路；否则，不存在欧拉环路。其中特别地，若奇度数的顶点恰有两个，则必然存在以这两个顶点为起点、终点的欧拉通路。

构造欧拉环路的一种算法，过程大致如下。

从任一顶点出发做一趟深度优先搜索，依次记录沿途经过的各边并随即将其从图中删除；一旦有顶点度数归零，也随即将此顶点删除。一旦回到起点，即得到一条欧拉子环路。
此时若还存在已访问但尚未被删除的顶点，则任选其一并从它出发，再做一趟深度优先搜索，过程相同。
每次所得新的子环路，都需要在搜索的起始点处与此前的子环路合并为一条更大的子环路。
当不剩任何顶点时，算法结束，当前的子环路即为原图的一条欧拉环路。

如果采用邻接表实现图结构，则以上算法中的每一基本操作（访问或删除当前顶点的一条关联边、访问度数非零的顶点、删除度数为零的顶点、将两条子环路在公共顶点处合并等）都可以在常数时间内完成，故总体运行时间线性正比于原图自身的规模。

上述关于欧拉环路存在性的判定依据以及环路的构造算法不仅适用于无向图，实际上也不难推广至有向图。

考查如图 x6.4(a)所示的有向图实例。

首先，经核对确认各顶点的出、入度数分别相等，故可判定该有向图存在欧拉环路。
接下来，从任一顶点出发做深度优先搜索。比如，若从顶点 C 出发，可能如图 (b)所示得到一条子环路： { C A D }
删除已访问过的边，并继续从顶点 C 出发做深度优先搜索，即可能如图 (c)所示得到子环路： { C D B } 并与上一子环路在顶点 C 处合并为： { C D B C A D }
删除已访问过的边，并删除度数为零的顶点C和D之后，继续从已经访问但尚未删除的任一顶点出发做深度优先搜索。实际上此时只能从顶点B出发，得到子环路{ B, A }，并与上一子环路在顶点B处合并为： { C D B A B C A D }

6-11 分析 BFS 中 CROSS 在无向图和有向图中的情况

根据此前的分析，无向图中任意一对邻接顶点在 BFS 树中的深度之差至多为1。因此在经过广度优先搜索之后，无向图的各边无非两类：树边，亦即被 BFS 树采用的边；跨边，亦即联接于来自不同分支、深度相同或相差一层的两个顶点之间的边。

类似地，有向图中：

每一条边 (v, u)均必然满足： $d e pt h (u) \leq d e pt h (v) + 1$ 这一不等式取等号时，(v, u) 即是（由 v 指向 u 的）一条树边。
若满足： depth (u) = depth (v) 则 v 和 u 在 BFS 树中分别属于不同的分支，(v, u) 跨越于二者之间。
若满足： depth(u) < depth(v) 则在 BFS 树中，u 既可能与 v 属于不同的分支，也可能就是 v 的祖先。

6-12 括号引理

括号引理

在有向图 DFS 的实例中，

若从 a 开始 DFS 可以得到的 DFS-Tree 是这样：

若从 d 开始 DFS，得到的 DFS-Tree 则是这样：

若规定某个节点的活跃期为 $a c t i v e [v] = (d T im e [v], f T im e [v])$ ，表明该节点从发现到访问结束的时间间隔，可以发现，对于有向图 G=(V, E)及其任一 DFS 森林，有：

若 u 是 v 的后代，则 $a c t i v e [u] \subseteq a c t i v e [v]$

若 u 是 v 的祖先，则 $a c t i v e [u] \supseteq a c t i v e [v]$

若 u 与 v 无关，则 $a c t i v e [u] \cap a c t i v e [v] = \emptyset$

这就是括号引理——仅凭 status、dTime 和 fTime 就可以对各边分类；

指向原始笔记的链接

证明 v 是 u 的祖先，当且仅当 $[d T im e (v), f T im e (v)] \supseteq [d T im e (u), f T im e (u)]$ 先证明“仅当”。若 v 是 u 的祖先，则遍历过程的次序应该是“v 被发现…u 被发现…u 被访问完毕…v 被访问完毕”。也就是说，u 的活跃期包含于 v 的活跃期中。由此也可得出一条推论：在任一顶点 v 刚被发现的时刻，其每个后代顶点 u 都应处于 UNDISCOVERED 状态。

反之，若 u 的活跃期包含于 v 的活跃期中，则意味着当 u 被发现（由 UNDISCOVERED 状态转入 DISCOVERED 状态）时，v 应该正处于 DISCOVERED 状态。

因此，v 既不可能与 u 处于不同的分支，也不可能是 u 的后代。故“当”亦成立。实际上由以上分析可进一步看出，此类顶点活跃期之间是严格的包含关系。

证明 v 与 u 无承袭关系，当且仅当 $[d T im e (v), f T im e (u)] \cap [d T im e (u), f T im e (u)] = \emptyset$ 作为 1) 的推论，“当”显然成立，故只需证明“仅当”。考查没有承袭关系的顶点 v 与 u，且不妨设 dTime(v) < dTime(u)。于是根据 1)，只需证明 fTime(v) < dTime(u)。

否则，若 dTime(u) < fTime(v)，则意味着当 u 被发现时，v 应该仍处于 DISCOVERED 状态。此时，必然有一条从 v 通往 u 的路径，且沿途的顶点都处于 DISCOVERED 状态。此时在 DFS()算法的函数调用栈中，沿途各顶点依次分别存有一帧。在 DFS 树中，该路径上的每一条边都对应于一对父子顶点，故说明 u 是 v 的后代——这与假设矛盾。

6-13 括号引理应用

题目：在起始于顶点 s 的 DFS 过程中某时刻，设当前顶点为 v，证明任一顶点 u 处于 DISCOVERED 状态，当且仅当 u 处于 s 通往 v 的路径的沿途（换言之，DFS 树中 u 是 v 的祖先）

由题所述条件，可知必有： dTime(u) < dTime(v) < fTime(u)

于是由以上根据顶点活跃期之间相互包含关系的结论，必有： dTime(u) < dTime(v) < fTime(v) < fTime(u) 亦即： $[d T im e (v), f T im e (v)] \subseteq [d T im e (u), f T im e (u)]$ 故知 u 必为 v 的祖先。

由以上规律亦可进一步推知：起始顶点 s 既是第一个转入 DISCOVERED 状态的，也是最后一个转入 VISITED 状态的，其活跃期纵贯整个 DFS()算法过程的始末；在此期间的任一时刻，任何顶点处于 DISCOVERED 状态，当且仅当它属于从起始顶点 s 到当前顶点 v 的通路上——这一通路的作用，也就相当于第4.4.1节所介绍的忒修斯的线绳。

6-16 Prim 算法通过扰动消除由重复边引起的歧义

说明：试说明，对于整数权重的网络，可通过足够小的扰动，在不影响 Prim 算法正确性、计算过程及复杂度的前提下，消除由（同为某一割的极短跨边的）重复边引起的歧义。

设原图共含 v 个顶点、e 条边，且不妨假定 v - 1 ⇐ e。若各边权重（按输入次序）依次为： W = { w1, w2, w3, …, we } 且不妨设其中各边权重不致完全相等，则可将其替换为： W’ = { w1 + 1/e^2 , w2 + 2/e^2 , w3 + 3/e^2 , …, we + e/e^2 = we + 1/e } 也就是说，各边的权重均有所增加，且增量为以1/e^2为公差的算术级数。

请注意，所有各边权重的扰动量总和不过： (1 + 2 + 3 + … + e)/e^2 = (1 + e)/2e < 1 更重要的是，即便 W 中可能存在等权的边，在如此构造的 W’中各边的权重也必然互异。于是，对其采用 Prim（以及稍后介绍的 Kruskal）算法将不致出现歧义情况，其最小支撑树 Tm’亦必然唯一确定。也就是说，W’的任何一棵支撑树 T’都应满足： |Tm’| ⇐ |T’| … (1) 这里的|Tm’|和|T’|分别表示 Tm’和 T’的总权重。特别地，等号仅在 T’ = Tm 时成立。

不等式(1)的左、右同时向下取整后，应该依然成立，亦即： $⌊ ∣ T_{m}^{^{'}} ∣ ⌋ \leq ⌊ ∣ T^{^{'}} ∣ ⌋ .................................................... (1^{'})$

既然|W| = |W’| = e，故二者的所有支撑树之间必然存在一一对应的关系。考查如此对应的每一对支撑树 T 和 T’。既然它们各自都恰好包含 v - 1 条边，故应有： 0 < |T’| - |T| < (v - 1)∙(1/e) ⇐ 1 也就是说，必有： $⌊ ∣ T^{^{'}} ∣ ⌋ = ∣ T ∣................................................... (2)$

特别地，若设与 Tm’对应的（W 的）支撑树为 Tm，则也应有 $⌊ ∣ T_{m}^{^{'}} ∣ ⌋ = ∣ T_{m} ∣.................................................. (3)$

综合(3)、(1’)和(2)可知，对于 W 的任何一棵支撑树 T，都有： $∣ T_{m} ∣ = ⌊ ∣ T_{m}^{^{'}} ∣ ⌋ \leq ⌊ ∣ T^{^{'}} ∣ ⌋ = ∣ T ∣$ 由此可见，Tm 必然是 W 的（一棵）最小支撑树。

另一种“方法”似乎更加巧妙，但实际上并不可行，故在此特作说明。仿照以上技巧，将原图各边的权重依次替换为： W’ = { w1 + 1/2, w2 + 1/2^2 , w3 + 1/2^3 , …, we + 1/2^e } 也就是说，各边权重均有所增加，且增量构成以1/2为公比的几何级数，其总和不过： 1/2 + 1/2^2 + 1/2^3 + … + 1/2^e < 1 同时，即便 W 中可能存在等权的边，在如此构造的 W’中各边的权重同样必然互异。因此与上一方法同理，亦可以消除最小支撑树构造过程中的歧义。然而不幸的是，这种“方法”要求计算机的数值精度达到1/2^e——与边数 e 呈负指数相关，或者说数位与 e 呈线性相关。也就是说，随着 e 的增加，计算机的字长很快就会溢出。而反观上一方法，数值精度为1/e^2，相对而言不致轻易就溢出。

这种扰动的方法是否可以推广至实数权重的网络？以上方法之所以行之有效，是因为事先能够在不等权的边之间，确定边权重的最小差值（1），从而既能够保证 W’中的各权重彼此互异，同时又能保证通过向下取整运算，可以从|T’|确定对应的|T|。若权重可以取自任意实数，则这两个性质不能直接兼顾。当然，若各边权重均取自浮点数（正如实际计算环境中的情况），则仍可以套用上述方法，只不过需要做必要的预处理——通过统一的放缩，将各边的权重转换为整数。

6-17 Prim 算法的极短跨边问题

说明：上图中出于简洁的考虑，将通路 us 和 vt 分别画在构成割的两个子图中。然而这样有可能造成误解，比如读者或许会认为，组成这两条通路的边也必然分别归属于这两个子图。试举一实例说明，us 或 vt 均可能在两个子图之间穿越多（偶数）次——亦即，除了该割的最短跨越边 uv，最小支撑树还可能采用同一割的其它跨越边，其长度甚至可能严格大于|uv|。

一个（组）通用的实例如图 x6.5所示。这里的子集 U 包含2n 个顶点（白色），其中2n - 1条非跨越边的权重依次为： $W_{U} = {3 n, 4 n, 3 n, 4 n, ..., 3 n}$

补集 $V U$ 也包含 2n 个顶点（黑色），其中2n - 1条非跨越边的权重依次为： $W_{V U} = 4 n, 3 n, 4 n, 3 n, ..., 4 n$ 在这两个子集之间，共有2n 条跨越边，其权重依次为： X = { 1, 2, 3, 4, …, 2n - 1, 2n }

不难验证，该图的最小支撑树唯一确定——由权重不超过 3n 的所有4n - 1条边组成，亦即图 x6.5 中所有的粗边。由图易见，该支撑树就是一条通路，它在割的两侧总共穿越 2n 次——（权重为1的）最短跨越边只是其中之一。

实际上，X 中各跨越边的权重未必需要按次序排列。另外，基于二部图，完全可以构造出更为精简的实例。

6-18 通过拓扑排序检查是否是 DAG

描述：利用“有向无环图中极大顶点入度必为零”的性质，实现一个拓扑排序算法，若输入为有向无环图，则给出拓扑排序，否则报告“非有向无环图”。该算法时间、空间复杂度各是多少？

策略（伪代码）

将所有入度为 0 的顶点存入栈 S，取空队列 Q //O (n)

从栈中输出所有零入度的顶点，最后得到的序列是顺序的零入度顶点：
while ( ! S.empty() ) { //O(n)
	Q.enqueue( v = S.pop() ); //栈顶v转入队列
	for each edge( v, u ) //v的邻接顶点u若入度仅为1
		if ( u.inDegree < 2 ) S.push( u ); //则入栈
	G = G \ { v }; //删除v及其关联边（邻接顶点入度减1）
} //总体O(n + e)
return |G| ? "NOT_A_DAG" ： Q; //残留的G空，当且仅当原图可拓扑排序
指向原始笔记的链接

这里，栈 S 和队列 Q 的初始化共需 O(n)时间。主体循环共计迭代 O(n)步，其中涉及的操作无非以下五类：

出、入栈，共计 O (n)次；
入队，共计 O (n)次；
递减邻接顶点的入度，共计 O (e)次；
删除（零入度）顶点，共计 O (n)个；
（删除顶点时一并）删除关联边，共计 O (e)条。

以上各类操作均属于基本操作，故总体运行时间为 O(n + e)，线性正比于原图的规模。

空间方面，除了原图本身，这里引入了辅助栈 S 和辅助队列 Q，分别用以存放零入度顶点和排序序列。不难看出，无论是 S 或 Q，每个顶点从始至终至多在其中存放一份，故二者的规模始终不超过 O(n)。实际上，通过更进一步地观察还可以发现，S 和 Q 之间在任何时刻都不可能有公共顶点，因此二者总体所占的空间亦不过 O(n)。

请注意，既然不是基于深度优先搜索，故亦无需维护各顶点的时间标签及状态、各边的分类。因此相对于基于深度优先搜索的拓扑排序算法而言，这一实现方式所需的附加空间更少——尤其是对于稠密图而言。

6-21 以 PFS 设计 prioUpdater 实现 BFS、DFS

template <typename Tv, typename Te> struct BfsPU { //针对BFS算法的顶点优先级更新器
   virtual void operator()( Graph<Tv, Te>* g, int uk, int v ) {
      if ( g->status( v ) == UNDISCOVERED ) //对于uk每一尚未被发现的邻接顶点v
         if ( g->priority( v ) > g->priority( uk ) + 1 ) { //将其到起点的距离作为优先级数
            g->priority( v ) = g->priority( uk ) + 1; //更新优先级（数）
            g->parent( v ) = uk; //更新父节点
         } //如此效果等同于，先被发现者优先
   }
};

比如，对于任何一个图结构 g，若顶点为 char 类型，边为 int 类型，则可以通过如下形式的调用，基于 PFS 框架完成对 g 的广度优先搜索。g->pfs( 0, BfsPU() ); 与 Dijkstra 算法的顶点优先级更新器 DijkstraPU() 做一对比，即可看出，这里的 BfsPU() 只不过将 $u_{k}$ 到邻接顶点 v 的距离 g->weight(uk, v) 统一替换为1——也就是说，所谓的广度优先搜索实际上完全等效于，在所有边权重均为1的图中应用 Dijkstra 算法构造最短路径树。就此意义而言，广度优先搜索也可以视作 Dijkstra 算法的一个特例。

template <typename Tv, typename Te> struct DfsPU { //针对DFS算法的顶点优先级更新器
   virtual void operator()( Graph<Tv, Te>* g, int uk, int v ) {
      if ( g->status( v ) == UNDISCOVERED ) //对于uk每一尚未被发现的邻接顶点v
         if ( g->priority( v ) > g->priority( uk ) - 1 ) { //将其到起点距离的负数作为优先级数
            g->priority( v ) = g->priority( uk ) - 1; //更新优先级（数）
            g->parent( v ) = uk; //更新父节点
            return; //注意：与BfsPU()不同，这里只要有一个邻接顶点可更新，即可立即返回
         } //如此效果等同于，后被发现者优先
   }
};

同样地，对于任何一个图结构 g，若顶点为 char 类型，边为 int 类型，则可以通过如下形式的调用，基于 PFS 框架完成对 g 的深度优先搜索。 g->pfs( 0, DfsPU() );

6-22 旅行商问题：找出哈密尔顿环路

描述：所谓旅行商问题，要求在任意 n 个城市的所有哈密尔顿环路中，找出总交通成本最低者。该问题属于经典的 NPC 问题，多数学者相信不存在多项式算法。试证明：若城市及其之间的交通成本可描述为遵守三角不等式（从A到B再到C的距离永不少于从A到C的距离）的带权网络，且已构造出对应的最小支撑树，则可在 O(n)时间内找出一条哈密尔顿环路，其交通成本不超过最优成本的两倍。

借助最小支撑树构造近似的旅行商环路的过程及原理，如图 x6.6所示。对于遵守三角不等式的任一带权网络 G，若其最小支撑树 MST（由图中灰色各边组成）已知，则只需将其中的每一条边，替换为方向互逆的一对边（黑色），即可相应地得到一条环路 W。

此处互逆的一对边，指的是把无向图的边化为双向的有向图的边。

于是，若将 MST 和 W 的总权重分别记作|MST|和|W|，则显然有： |W| = 2∙|MST| … (1)

将理想的旅行商环路（traveling salesman tour）记作 TST。作为一条环路，从 TST 中删除任何一条边 e 之后，都应得到一条纵贯所有顶点的通路 TST(e)，这条通路也可视作原图的一棵支撑树。因此，其长度（沿途各边的权重总和）应不小于最小支撑树的总长，亦即： |MST| ⇐ |TST(e)| < |TST| … (2)

综合(1)、(2)两式，即有： |W| < 2∙|TST| 也就是说，环路 W 的总长度不超过旅行商环路的两倍。

当然，严格地说至此 W 还不是一条旅行商环路——它经过每个顶点至少两次，而不是恰好一次。为此，只需对其遍历一趟，沿途所遇的顶点一旦在此前业已经过，则一概忽略并跳过，而改为一条直接联接的“捷径”。当最终重新回到遍历起点时，即得到了一条严格意义上的环路 apprTST（图中以虚线示意）。因为这里的带权网络遵守三角不等式，故在上述遍历过程中被跳过各边的总长，不致超过各段捷径的总长，这意味着 apprTST 的总长相对于 W，只能进一步地缩短。

6-23 合成数法消除 Prim 和 Dijkstra 算法的歧义性

描述：合成数（composite number）法，是消除图算法歧义性的一种通用方法。首先，在顶点标识之间约定某一次序。比如，顶点标识为整数或字符时，可直接以整数或字符为序；对于字符串等标识，不妨按字典序排列。于是，若边(v, u)权重为 w，则对应的合成数取作向量： (w, min(v, u), max(v, u)) 如此，任何两条边总能明确地依照字典序比较出大小。试在 Prim 算法和 Dijkstra 算法中引入这一方法，以消除其中的歧义性。

采用这一方法，实质的调整无非只是比较器的重新定义，算法的整体框架及流程均保持不变。具体地，也就是将原先各边的权重，替换为其对应的合成数，并按照字典序判定各边的优先级。

反观 Prim 算法。在最短跨越边同时存在多条时，该算法可以任取其中之一。虽然如此必然能够构造出一棵最小支撑树，但却不能保证其唯一确定性。
对于所有边的权重为整数或浮点数的情况，此前介绍过通过扰动使之唯一确定化的技巧。按照这一方法，输入序列中各边的扰动量严格单调递增，故在扰动之后，原先权重相等的边必然可以按照“前小后大”的准则判定相对的优先级。从这个角度来看，其效果完全等同于将各边的权重依次替换为如下合成数： W’ = { (w1, 1), (w2, 2), (w3, 3), …, (we, e) }

请注意，合成数方法不再局限于整数或浮点数的权重，因此适用范围更广。

6-24 考查负权边和负权环对 Prim 和 Dijkstra 算法的影响

包含负权边的图，Prim 算法是否可行？不妨设带权网络 G 中各边权重的最小值为-δ < 0，此类网络的最小支撑树同样亦必然存在，且可以套用 Prim 算法构造出来。

为更清楚地看出这一点，可以令 G 所有边的权重统一地增加2δ，即可得到另一带权网络 G’，且 G’中各边权重均为正数，故 G’的最小支撑树必然存在。既然 G 和 G’的顶点与边一一对应，故其支撑树亦必一一对应。

实际上，无论各边的权重如何取值，支撑树所采用边的总数必然固定为v - 1，其中v为顶点总数。因此就总权重而言，G的每一棵支撑树与G’所对应支撑树的差异均为： 2δ∙(v - 1) 因此，原网络G的最小支撑树必然存在，而且必与G’的最小支撑树对应。

若不含负权环，仍可以定义 SPT，此时 Dijkstra 算法是否可行？依然可行。

Bellman-ford 算法可以应用在负权环的图中，Dijkstra 算法不可以。

6-25、26 边权重复时极小支撑树问题

描述：各边权重未必互异时，带权网络的“最小生成树”未必唯一，故应相应地，将其改称作“极小支撑树”更为妥当。对于任一此类的带权网络 G，试证明：

每一割的极短跨边都会被 G 的某棵 MST 采用上图已在“各边权重互异”的前提下，证明了 Prim 算法的正确性。在废除这一前提之后，证明的技巧依然类似。

反证。如该图所示，假设 uv 是割(U : V\U)的极短跨越边（之一），但 uv 却未被任何极小支撑树采用。任取一棵极小支撑树 T，则 T 至少会采用该割的一条跨越边 st。于是同理，将 st 替换为 uv，将得到另一棵支撑树 T’，而且其总权重不致增加。这与假设相悖。

G 的每棵 MST 的每一条边，都是某一割的极短跨边任取 G 的一棵极小支撑树 T，考查其中的任何一条树边 uv。将该边删除之后，T 应恰好被分成两棵子树，它们对应的两个顶点子集也构成 G 的一个割(U : V\U)。实际上，uv 必然是该割的极短跨越边（之一）。否则，与 1)同理，只需将其替换为一条极短跨边 st，即可得到一棵总权重更小的支撑树 T’——这与 T 的极小性矛盾。
举例说明，在允许多边等权的图 G 中，即使某棵支撑树 T 的每一条边都是 G 的某一割的极短跨边，T 的也未必是 G 的 MST。首先不难验证，每一条边都是 G 某一割的极短跨越边：ac 为全图的最短边；ad 则为割： ({ a, b, c } : { d }) 的极短跨越边（之一）——根据对称性，其余权重同为5的各边亦是如此。

既然该网络的支撑树都由三条边组成，故如图(b)和(c)所示，总权重为3 + 5 + 5 = 13 的支撑树必然是极小的。然而如图(d)所示，同样亦由三条极短跨越边构成的支撑树，总权重却为15，显然并非极小支撑树。

6-27 证明 Prim 算法在多边等权时亦然成立

描述：多边等权可能导致同一割拥有多条最短跨边，试证明 Prim 算法的贪心迭代策略依然行之有效。（hint: 只需证明， $T_{k}$ 是某棵 MST，则 $T_{k + 1}$ 也必然是（尽管可能与前一棵不同的） MST 的子树）

任取一棵极小支撑树 T* = (V, E* )，以下采用数学归纳法证明： ==对于 Prim 算法过程中所生成的每一棵（子）树 $T_{k}$ ，都可以在总权重不致增加的前提下，将 T* 转换为其一棵超树==

如果这是事实，则意味着 Prim 算法最终生成的 $T_{n}$ 也是一棵极小支撑树。作为归纳基，以上命题对于 T1 显然成立。

以下，假定上述命题对于 $T_{1}, ..., T_{k - 1} （ 2 \leq k ）$ 均成立。如图 x6.8 所示，考查： $T_{k} = (V_{k - 1} \cup u, E_{k - 1} \cup vu)$ 且不妨设边 $vu \in / E^{*}$ 。

既然 T* 是 $T_{k - 1}$ 的超树，故在将后者从前者中删除之后， $T^{*} T_{k - 1}$ 应该是个非空的森林。将顶点 u 在其中所属的子树记作 $T_{u}^{*}$ 。在 T* 中，子树 $T_{k - 1}$ 与子树 $T_{u}^{*}$ 之间必然有且仅有一条边相联，设为 st （有可能 s = v 或 t = u，但是不能同时成立）。

现在，在 T* 中将 st 替换为 vu。经如此转换之后，T* 的连通性和无环性依然满足，故仍是原图的一棵支撑树。

就权重而言，T* 新、旧两个版本之间的差异为|vu| - |st|。鉴于 Prim 算法挑选的 vu 必然是极短跨越边，故新版本的权重不致增加（当然，也不可能下降）。由此可见，归纳假设对 Tk 也依然成立。

6-28 Kruskal 算法

Kruskal 算法的步骤：

将每个顶点视作一棵树，并将所有边按权重非降排序；
依次考查各边，只要其端点分属不同的树，则引入该边，并将端点所分别归属的树合二为一
如此迭代，直至累计引入 n-1 条边时，即得到一棵 MST。

试证明：

算法过程中引入的每一条边，都是某一割的极短跨边（因此亦必属于某棵 MST）考查 Kruskal 算法每一步迭代中所引入的边 vu。在此步迭代即将执行之前，v 必属于当时森林中的某棵子树，将其记作 Tv。Tv 及其补集，构成原图的一个割。不难看出，vu 既然（作为当时不致造成环路的极短边）被选用，则它必然也是该割的极短跨越边。
算法过程中任一时刻，由已引入的边所构成的森林，必是某棵 MST 的子图任取一棵极小支撑树 T* = (V, E* )，以下采用数学归纳法证明： BBFABBA6;">对于 Kruskal 算法过程中的每一个森林 Fk 都可以在总权重不致增加的前提下，将 T* 转换为其一棵超树

如果这是事实，则意味着 Kruskal 算法最终生成的 Tn = Fn 也是一棵极小支撑树。作为归纳基，以上命题对于 F0显然成立。

以下，假定上述命题对于 $F_{0}, ..., F_{k - 1} (1 \leq k)$ 均成立。如图 x6.9所示，考查： $F_{k} = (V, E_{k - 1} \cup vu)$ 且不妨设边 $vu \in / E^{*}$ 。

将 v 和 u 所属的子树分别记作 Tv 和 Tu。既然 T* 是 $F_{k - 1}$ 的超树，故 T* 中必然在 Tv 和 Tu 之间存在（唯一的）一条通路。该通路可能就是 vu 之外的另一跨越边，也可能是转辗穿过其它子树的一条迂回通路。无论如何，如图所示将该通路的起始边设为 st。现在，在 T* 中将 st 替换为 vu。经如此转换之后，T* 的连通性和无环性依然满足，故仍是原图的一棵支撑树。就权重而言，T* 新、旧两个版本之间的差异为|vu| - |st|。鉴于 Kruskal 算法挑选的 vu 必然是极短跨越边，故新版本的权重不致增加（当然，也不可能下降）。由此可见，归纳假设对 Fk 也依然成立。

6-29 说明最坏情况的 Kruskal 算法

该实例中，原网络中的 n - 1个顶点构成完全图 $K_{n - 1}$ ，其中各边的权重相对不大；最后一个顶点 u，则仅通过一条权重足够大的边 vu 与完全图相联。若将({u} : Kn-1)视作割，则 vu 是唯一的跨越边。因此，尽管该边的权重在全局最大，但该带权网络的任何一棵极小支撑树 T* ，都必会采用该边。而按照 Kruskal 算法的策略，vu 必然是作为最后一条边接受检查；在此前，该算法也必然已经遍历过 Kn-1中所有的边，累计耗时总量为： n(n - 1)/2 + 1 = Ω(n^2)

6-30 并查集

Kruskal 算法涉及的操作不过两类：

T=find(x)  //查询元素(顶点)x所属的等价类(子树)T
union(x,y) //将元素y所属的等价类(子树)，合并至元素(顶点)x所属的等价类(子树)

实现该数据结构。并查集中的等价类，可以视作某一全集经划分之后得到的若干互不相交的子集。最初状态下，全集中的每个元素自成一个子集，并以该元素作为其标识。此后，每经过一次 union(x, y)操作，都将元素 y 所属的子集归入元素 x 所属的子集，并继续沿用元素 x 此前的标识。

一种可行的方法是，将并查集中的所有元素组织为一个向量，其中的子集则以多叉树的形式实现。以由8个元素组成的并查集 {{A}, {B}, {C}, {D}, {E}, {F}, {G}, {H}} 为例，其初始状态如图 x6.11所示。如以上约定，各元素自成一棵树，故 parent 值统一取作-1。如此，子集的合并操作可对应于树的合并操作。既然元素所属的子集就是其所属的树，故对二者亦不必刻意区分。比如，在经过 union(D, F)和 union(G, B)操作之后，以上并查集的内部结构及逻辑结构如图 x6.12所示。其效果等同于，将 F 所属的树归入 D 所属的树，并继续沿用原标识 D；将 B 所属的树归入 G 所属的树，并继续沿用原标识 G。这里约定，每个子集的标识就是其所对应的树根元素。于是为了实现 find(x)操作，只需从元素 x 出发找到其对应的树根。为此，只需要记录每个元素的父节点——亦即其在向量中的秩。比如，元素 F 对应的 parent 值从初始的-1修改为3，指向元素 D；元素 B 对应的 parent 值从初始的 -1修改为6，指向元素 G。

以下如图 x6.13所示，经 union(D, A)和 union(F, H)之后，元素 A 和 H 都被归入以元素 D 为根（标识）的树（子集）中；经 union(E, C)之后，元素 C 被归入元素 E 所属的树中。请留意这里对有关元素 parent 值的设置，以及逻辑上树形结构的对应变化。

以下，假设继续执行 union(B, A)操作。为此可如图 x6.14所示，首先顺着 parent 的指示找到元素 B 和元素 A 各自所属的树根（子集标识）G 和 D；再通过将元素 D 的 parent 值从-1修改为6（指向元素 G），从而将树 D（对应的子集）整体归入树 G（对应的子集）。

以下，假设继续执行 union(C, F)操作。为此可如图 x6.15所示，首先顺着 parent 的指示找到元素 C 和元素 F 各自所属的树根（子集标识）E 和 G；再通过将元素 G 的 parent 值从-1修改为4（指向元素 E），从而将树 G（对应的子集）整体归入树 E（对应的子集）。由于并查集的 union()操作并不可逆，故至此以后该结构将不会再有实质性的调整。

这样实现的 find ()和 union ()接口的复杂度是多少？形成的 Kruskal 算法的时间复杂度是多少？无论 find()或 union()，都需要首先确定相关元素所属子集的标识（树根）。为此，需要沿着 parent 的指示不断上行，因此执行时间主要取决于元素在树中所处的深度；就最坏情况而言，取决于树的高度。然而按照目前的策略，我们并不能有效地控制树高。

仍以如图 x6.11所示的初始并查集为例，假若接下来依次执行： union(G, H), union(F, G), union(E, F), union(D, E), union(C, D), union(B, C), union(A, B) 则不难验证，各次 union()操作所需的时间将按算术级数递增。一般地在最坏情况下，对于包含 n 个元素的并查集，以上过程共需 O(n^2 )时间，单次操作平均需要 O(n)时间——退化到蛮力算法。相应地，基于该版本并查集的 Kruskal 算法，可能平均而言每步迭代都需要线性时间，累计共需 O(n∙e)时间。

为有效控制树的高度，还可采用其它的策略。比如在合并树时，可以采取“低者归入高者” 的策略。也就是说，比较待合并的树的高度，并倾向于将更低者归入更高者。仍以如图 x6.14所示的并查集为例，以下同样执行 union(C, F)。在找出对应的树 G 和 E 之后，经比较发现前者更高。故与如图 x6.15所示的合并方向相反，只要改为将树 E 归入树 G，则如图 x6.16所示，合并之后的树高即可由3降至2。当然，为此还需要给每个元素增添一个域，以动态记录其高度：初始统一取作0；合并时若两树高度相等，则合并后树根的高度值相应地递增；若高度不等，则无调整。最后，为了遵守此前关于子集标识的沿用约定，还有可能需要交换原先的两个树根——比如此例中的元素 E 和 G——包括它们各自的标识以及 parent 值。

有效控制树高的另一策略是路径压缩（path compression），它源自如下观察事实：就此问题而言，树中元素之间的拓扑联接关系并不重要；另外，因为仅涉及（沿 parent 指示的）上行查找而无需下行查找，故孩子的数目并不影响查找效率。因此，在对每个元素做查找的同时，可以将上行通路上的所有元素取出，再统一作为树根的孩子重新接入。如此，树可以尽可能地被平坦化，从而进一步地控制树高。

6-31 最短路径树不唯一问题

对照图(a)不难确认：该带权网络中各边的权重互异；相对于起始顶点 S，顶点 A 和 B 的最短距离分别为3和2。然而对于 A 而言，最短路径有两条（{ S, A }和{ S, B, A }），相应地如图 (b)和(c)所示有两棵最短路径树。

6-32 欧式最小支撑树

描述：若图 G 的顶点取自平面上的点，FFB8EBA6;">各顶点间均有联边且权重就是其间的欧氏距离，则 G 的最小支撑树亦称作欧氏最小支撑树（ Euclidean Minimum Spanning Tree, EMST)，记作 EMST(G)。

若套用 Kruskal 或 Prim 算法构造 EMST，各需要多少时间？带权网络 G 是由平面点集隐式定义的完全图，故若 G 由 n 个顶点构成，则所含边数应为： e = n(n - 1)/2 = O(n^2 )

因此若直接调用（借助优先级队列结构改进之后的）Prim 算法，渐进的时间复杂度应为： O ((n + e)∙logn) = $O (n^{2} \times l o g n)$
因此若直接调用 Kruskal 算法，渐进的时间复杂度应为： $O (e l o g n)$ = $O (n^{2} \times l o g n)$

试设计一个算法，在 O (nlogn)时间内构造出 EMST。（提示：Delaunay 三角剖分）由上可见，为了能够高效地构造欧氏最小支撑树，必须回避对多达Ω(n^2)条边的处理。为此，可以首先通过预处理，将由欧氏距离隐式定义的完全图，转化为如图 x6.18 所示的某种邻近图（proximity graph）；然后，再针对邻近图调用 Prim 之类的常规算法。

其中图(a)为三角剖分（triangulation），也就是原隐式完全图的任意极大平面子图。因每个子区域都是三角形，故此得名。不难发现，同一点集的三角剖分往往并不唯一确定——但其所保留的边总数固定，所分出的三角形总数也固定。

任一点集都有一个特殊的三角剖分，称作 Delaunay 三角剖分（Delaunay triangulation）。如图(b)所示，在这种三角剖分中，任意三角形的外接圆都不包含第四个点——亦即所谓的空圆性质（empty-circle property）。反观图(a)，其中三角形 efg 的外接圆内还有 c 点，故而不属于 Delaunay 三角剖分。

可以按照以下准则，从 Delaunay 三角剖分中剔除若干条边：

一条边被剔除，当且仅当以其为直径的圆中（除了该边的两个端点）还包含第三个点。如此保留下来的子图如图 (c)所示，即是所谓的 Gabriel 图（Gabriel graph）。读者不妨对照图 (b)和图 (c)，核对各边的确都是按照以上准则被保留或剔除。
进一步地，可以按照以下原则，从 Gabriel 图中再剔除若干条边：一条边被剔除，当且仅当以其为半径、分别以其端点为圆心的两个圆，不会同时包含第三个点。如此保留下来的子图如图 (d)所示，即是所谓的 RNG 图（relative neighborhood graph）。读者不妨对照图 (c)和图 (d)，核对各边的确都是按照以上准则被保留或剔除。
由上可见，Delaunay 三角剖分、Gabriel 图、RNG 图依次构成“超图-子图”的关系。

超图是什么？

在数学中，超图（Hypergraph）是一种广义上的图。不同于普通图的一条边只能连接两个顶点，超图的一条边可以连接任意数量的顶点。理论上，超图 H 是一个集合组 H=(X, E)，其中 X 是一个有限集合，该集合的元素被称为节点或顶点，E 是 X 的非空子集的集合，被称为超边或连接。因此，E 是 $P (X) ∖ {\emptyset}$ 的一个子集，其中 $P (X)$ 是 X 的幂集。

尽管图的边各有一对节点，而超边是节点的任意集合，因而能包含任意数量的节点。然而，通常的研究更倾向于每个超边连接的节点数相同的超图：k-均匀超图（每个超边都连接了 k 个节点）。因此，2-均匀超图就是图，3-均匀超图就是三元组的集合，依此类推。

举例：一个超图的例子，图示中包含了 $X = {v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}}$ 和 $E = {e_{1}, e_{2}, e_{3}, e_{4}} = {{v_{1}, v_{2}, v_{3}}, {v_{2}, v_{3}}, {v_{3}, v_{5}, v_{6}}, {v_{4}}}$

实际上进一步地还可以证明，如图 (d)和图 (e)所示，欧氏最小支撑树必是 RNG 图的子图。这一事实的证明方法和技巧，与教材第 6.11.5 节“最小支撑树必然采用极短跨越边”的证明极其相似，我们将此留给读者独立完成。

既然三角剖分是平面图，故以上介绍的所有邻近图亦是。根据习题6-3 结论，其所含边的总数必然与顶点数渐进地相当，从 O (n^2 )降低到 O (n)。

另一好消息是，以上邻近图均可在 O(nlogn)的时间内构造出来。因此这里的预处理通常并不会增加整体的渐进时间复杂度。

证明三角剖分的方法已是最优（最坏情况下构造 EMST 都需要Ω(nlogn)时间）对于任意平面点集 G，可以定义最近邻图（nearest neighbor graph，NNG）如下： FFB8EBA6;">边 pq 属于该图，当且仅当点 q 在 G\{p}中距离 p 最近(请注意，最近邻图是有向图)。也就是说，q 是 p 的最近邻，未必反之亦然。

考查经典的 ε-间距问题（ε-closeness）： FFB8EBA6;">设 P 为由任意 n 个实数构成的集合，对于任意的ε > 0，判定 P 中是否存在两个实数的差距不大于ε 该问题的难度，已经证明为ε(nlogn)。

实际上可以证明，最近邻图必然是欧氏最小支撑树的子图。特别地，该图中的最短边，即是所谓点集 G 中的最近点对（nearest pair）。不难看出，ε-间距问题可在线性时间内归约至最近点对问题，而最近点对问题又可以进一步地在线性时间内归约至欧氏最小支撑树问题。根据线性归约的传递性，ε-间距问题可在线性时间内归约至欧氏最小支撑树问题。于是自然地，Ω(nlogn)的复杂度下界，亦适用于欧氏最小支撑树问题。这意味着，在没有其它附加条件的前提下，以上所设计的 O(nlogn)算法，应该已经属于最坏情况下最优的。

🌰Senjl's Digital Garden🐉

Recent writing

Welcome to Senj's Digital Garden

4-地址空间

5-进程

探索