22.1-6 ?給出O(V)時間算法判斷有向圖G是否存在一個通用匯點(universal sink)。通用匯點指的是入度為|V|-1，出度為0的節(jié)點。

思路：

考慮圖的鄰接矩陣A，假設i為通用匯點，則對于0<=j<n，有A[i][j]=0，且對于所有0<=k<n and k != i，有A[k][i] = 1，注意這里k!=i

相當于在子矩陣A[0..i][0..i]的右邊和下邊造了一個圍墻，最下邊全是0，最右邊除了右下角外全是1

那么可以令游標從矩陣左上角開始，遇1向下，逢0向右，直到行或列超出矩陣A的界限，注意不是子矩陣。此時若游標所在行沒有超出界限，那和這個行號 r 就可能是通用匯點編號。

接下來再根據(jù)定義驗證 r 是否就是通用匯點。因為可能存在以下的情況：

x x x x 1 x x x x x x x 1 x x x x x x x 1 x x x x x x x 1 x x x 0 0 0 0 0 0 0 0 x x x x 0 x x x x x x x 0 x x x x x x x 0 x x x

矩陣第5行所表示的節(jié)點顯然不是通用匯點。

?

22.2-7 ?職業(yè)摔跤手劃分

思路：可歸結為對先廣生成樹進行著色，相鄰層顏色不同。若發(fā)現(xiàn)有連接相同顏色節(jié)點的回邊，則劃分失敗。發(fā)生這種情況，可能是相同層內(nèi)的節(jié)點間有邊，若與其他非相鄰層間同色節(jié)點之間有邊。

最后，相同顏色的劃分為一組，劃分完畢。

?

22.2-8 ?樹的直徑

思路：任意節(jié)點出發(fā)進行先廣遍歷，找到最長路徑的末端節(jié)點u，再從u出發(fā)進行先廣遍歷，最長路徑即為樹的直徑。

?

22.2-9 ?無向圖G，找出分別以正、反向通過每條邊的路徑

思路：任意節(jié)點出發(fā)，深度優(yōu)先遍歷，節(jié)點可以訪問任意次，但保持每條邊只訪問一次，在此過程中不斷把訪問到的邊在前進方向末端的節(jié)點加入到路徑中。每處理完一棵先深生成子樹，再把根節(jié)點加入到路徑。直到處理完的有子樹，并返回到根節(jié)點。

?

22.3-13 對于有向圖G=(V,E)來說，如果u->v意味著圖G至多包含一條從u到v的簡單路徑，則圖G是單連通圖。給出算法判斷一個有向圖是否是單連通圖。

注：本題解法參考了http://blog.csdn.net/wdq347/article/details/11096945，涉及到的理論證明不再詳述，只列出思路。

首先說簡單解法，依次從每個點出發(fā)進行DFS，出發(fā)前，把全部節(jié)點置為白色。每棵DFS樹中只要發(fā)現(xiàn)forward edge或樹內(nèi)的cross edge，則圖G必不是單連通圖。

參考文章中給出了對于稠密圖的優(yōu)化解法。

簡單來說，就是分別考慮圖G的每個強連通分量，利用如下定理判斷連通分量是否是單連通圖（以下定理來自參考文章）

定理：圖G是強連通圖且DFS不含有forward edge或cross edge，G不是單連通圖當且僅當DFS樹滿足以下任意一個條件：

(1) 存在點v至少有兩條back edge；

(2) 存在點v只有一條back edge，且v的某個子結點x，low[x] <dfn[v]

(3) 存在點v，v至少有兩個子結點x,y，low[x] < dfn[v]，low[y] <dfn[v]

情況1表示v到某個祖先節(jié)點至少有兩條路徑，圖G必不是單連通圖；

情況2表示v的某個子節(jié)點與v的某個祖先存在路徑，再加上v有一條back edge，則v到某個祖先節(jié)點（不一定是前面提到的那個祖先節(jié)點）存在兩條路徑；

情況3表示v至少有兩個子節(jié)點通向了祖先節(jié)點，即v到某個祖先節(jié)點至少存在兩條路徑。

可惜的是，文章中給的代碼只適用于強連通圖或強連通分量，并沒有繼續(xù)處理分量圖的過程。

這里補上我對后續(xù)處理分量圖的理解。分量圖，從直觀上理解，就是把每個強連通分量分別壓縮為一個點后形成的圖。需要注意的是，壓縮為一個點后，原先這個分量的入邊都指向壓縮后的點；而分量的出邊則都從該點出發(fā)。分量圖是一個有向無環(huán)圖，那么就可以直接使用前面提到的簡單解法進行求解。

總結一下，對于稀疏圖，可直接使用簡單解法，復雜度為O(V+E)；對于稠密圖，可使用參考文章提出的解法，先判斷每個強連通分量是否為單連通圖，若全是，則再判斷分量圖是否為單連通圖，復雜度為O(V*V)

?

22.5-7 給定有向圖G(V,E)，所有結點對之間有單向或雙向路徑，則圖G半連通。請判斷一個圖是否半連通。

http://blog.csdn.net/wdq347/article/details/9995153 提到了一個引理：有向無環(huán)圖G(V,E)，G是半連通的當且僅當有一條路徑，這條路徑上有圖G中所有點。

接下來提到了解決方法，即先得到圖G的分量圖，再得到分量圖的拓撲序列，若序列中任意相鄰兩點間有邊（方向一定是序列中靠前的節(jié)點指向靠后的節(jié)點），則分量圖是半連通圖。又，強連通圖也是半連通圖，那么原始圖每個強連通分量是半連通圖，所以原始圖也是半連通圖。

轉載于:https://www.cnblogs.com/venux021/p/7400569.html

總結

以上是生活随笔為你收集整理的算法导论22章 基本图算法习题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。