ThinkSSL🔒 一键申购 5分钟快速签发 30天无理由退款 购买更放心 广告
# 一、综述 定义: ![](https://box.kancloud.cn/2016-02-02_56b02bd3a1b18.gif) # 二、代码 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]&gt;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可达 &amp;&amp; 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不可达 &amp;&amp; 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不可达 &amp;&amp; v到u可达</div><div>&amp;&amp; (v,u)不是G中的边</div><div>&amp;&amp; 存在另一个结点w &amp;&amp; w与v在同一个联通分支</div><div>&amp;&amp; w到u可达 &amp;&amp; f[w]&gt;f[u]&gt;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可达 &amp;&amp; v到u不可达</div><div>&amp;&amp; (u,v)不是G中的边 &amp;&amp;</div><div>存在另一个结点w &amp;&amp; w与v在同一个联通分支 &amp;&amp;</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]&lt;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]&lt;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不可达 &amp;&amp; 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可达 &amp;&amp; v到u不可达</div><div>&amp;&amp; (u,v)不是G中的边</div><div>&amp;&amp; 存在另一个结点w &amp;&amp; w与u在同一个联通分支</div><div>&amp;&amp; w到v可达 &amp;&amp; f[w]&gt;f[v]&gt;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 待解决,题目的意思不太懂,网上找了个答案,主要是其中的第四步不懂。 ![](https://box.kancloud.cn/2016-02-02_56b02bd3b7978.gif) 令所求图为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中的任意一个顶点 解释: 强连通分支: ![](https://box.kancloud.cn/2016-02-02_56b02bd3d0626.jpg) 分支图: ![](https://box.kancloud.cn/2016-02-02_56b02bd3e167f.jpg) 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为半连通。