第22章 图的基本算法 22.5 强联通分支
最后更新于：2022-04-01 07:36:12
# 一、综述
定义：
# 二、代码
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_5.cpp
# 三、练习
### 22.5-1
不变或减少
### 22.5-2
第一次DFS结果：
r u q t y x z s v w
G转置的结果：
q:y
r:
s:q w
t:q
u:r
v:s
w:q v
x:t z
y:r t u
z:x
第二次DFS的结果：
r
u
q y t
x z
s w v
### 22.5-3
简化后的算法不可行，证明如下。
在原算法中，过程总结为这样几步
（1）对图G作DFS，计算每个点的结束时间f
（2）将结点以f递减排序
（3）对图作转置，得到GT
（4）以f递减顺序对GT作DFS
（5）第二次DFS后得到的一个树里的点都属于同一个强联通分支
如果以DFS后的f递减排序，排序的结点有规律呢？
假设f[u]>f[v]，那么u和v的关系可能有几下四种情况
（1）u和v互相不可达
（2）u和v互相可达，即在同一个联通分支内
（3）u到v可达 && v到u不可达
（4）u到v不可达 && v到u可达 && (v,u)不是G中的边 && 存在另一个结点w && w与v在同一个联通分支 && w到u可达 && f[w]>f[u]>f[v]
以下将针对这四种情况做第（3）（4）操作，看是否能得到第（5）的结果
<table style="border-collapse: collapse; table-layout: fixed; margin-left: 0px;" height="242" width="865"><tbody><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.37278106508876%;"><div>对G做DFS后，f[u]>f[v]，u和v的关系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.25443786982248%;"><div>在GT中u和v的关系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.25443786982248%;"><div>在GT中对u做DFS，v是否会成为u的后继</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可达，即在同一个联通分支内</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可达，即在同一个联通分支内</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可达 && v到u不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可达 && v到u可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可达 && v到u可达</div><div>&& (v,u)不是G中的边</div><div>&& 存在另一个结点w && w与v在同一个联通分支</div><div>&& w到u可达 && f[w]>f[u]>f[v]</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可达 && v到u不可达</div><div>&& (u,v)不是G中的边 &&</div><div>存在另一个结点w && w与v在同一个联通分支 &&</div><div>u到w可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会。</div><div>虽然u到v可达。但由于f[w]<f[v]，会先对w做DFS，v已经是w的后继了，所以不会成为u的后继</div></td></tr></tbody></table>
由此可以知道，以f递减的顺序对GT作DFS，同一个连通分支的点会到一棵不树上，不是同一个连通分支的点不会到一棵树上。
再看本题的算法过程，总结为以下几步：
（1）对图G作DFS，计算每个点的结束时间f
（2）将结点以f递增排序
（3）以f递增的顺序对GT作DFS
（4）第二次DFS后得到的一个树里的点都属于同一个强联通分支
与上述步骤类似，我们先分析f递增排序后结点的关系，然后针对这些关系做第（3）步，分析是否能得到第（4）步的结果
<table style="border-collapse: collapse; margin-left: 0px; table-layout: fixed;" height="242" width="646"><tbody><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:50.05917159763313%;"><div>对G做DFS后，f[u]<f[v]，u和v的关系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:49.82248520710059%;"><div>在G中对u做DFS，v是否会成为u的后继</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可达，即在同一个联通分支内</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可达 && v到u可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可达 && v到u不可达</div><div>&& (u,v)不是G中的边</div><div>&& 存在另一个结点w && w与u在同一个联通分支</div><div>&& w到v可达 && f[w]>f[v]>f[u]</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>会。</div><div>此处不对。u和v不属于同一个联通分支，但v会成为u的后继</div></td></tr></tbody></table>
因此该算法不可行。
### 22.5-5
见[算法导论 22.5-5 O(V+E)求有向图的分支图](http://blog.csdn.net/mishifangxiangdefeng/article/details/8461683)
### 22.5-6
待解决，题目的意思不太懂，网上找了个答案，主要是其中的第四步不懂。
令所求图为G2，翻译一下：
STEP1：使用22.5中的算法计算出所有的强连通分支
STEP2：使用22.5中和算法计算出分支图G|SCC
STEP3：将G2的边集初始化为空
STEP4：将每个强连通分支中的顶点构成环。比如强连通分支a中有ea1,ea2,ea3,ea4这四个顶点，就在G2中加入边ea1->ea2,ea2->ea3,ea3->ea4,ea4->ea1
STEP5：把分支图的边加到G2中。比如分支图中有一条强连通分支a到强连通分支b的边，就在G2中加入一条ea到eb的边。其中ea是a中的任意一个顶点，eb是b中的任意一个顶点
解释：
强连通分支：
分支图：
G与G2有相同的强连通分支 ===> G2的顶点与G的顶点相同
G与G2有相同的分支图 ===> G2至少有着G|SCC中的边 ===> STEP5
G2有最小的边 ===> 具有最少边的强连通图是一个环，边的个数与顶点的个数相同 ===> STEP4
### 22.5-7
STEP1：使用22.5-5中的算法得到SCC。
STEP2：对SCC求拓扑序列(v1, v2, ……, vk)
STEP3：若在边SCC中存在边(v1,v2),(v2,v3),……,(vk-1,vk)，则图G为半连通。