【正文】 JYP 1 高級數(shù)據(jù)結構 (下 ) 教材： 《 數(shù)據(jù)結構（ C++描述） 》（金遠平編著，清華大學出版社） JYP 2 雙連分量 () 雙連分量在連通性方面比一般的連通分量具有更高的要求，生成雙連分量的操作也更復雜一些。 假設無向圖 G是連通的，下面給出雙連分量的正式定義。 定義： G的頂點 v是一個 關節(jié)點 當且僅當從 G中刪除 v及其關聯(lián)的邊后，剩下的圖至少有兩個連通分量。 JYP 3 例如 ， 在下面的連通圖 G6中 ， 頂點 1， 4和 7是關節(jié)點 。 JYP 4 定義：雙連通圖 是沒有關節(jié)點的連通圖。 例如，圖 G5是雙連通的： JYP 5 但圖 G6不是雙連通的。 在表示通信網(wǎng)絡的圖中，邊表示通信鏈路，頂點表示通信站點，關節(jié)點顯然是薄弱環(huán)節(jié)。 定義： 一個連通圖 G的 雙連分量 是 G的最大雙連通子圖。 JYP 6 圖 G6包含四個雙連分量，如下所示： JYP 7 不難發(fā)現(xiàn)，同一個圖的兩個雙連分量最多有一個共同頂點。由此可推出，一條邊不可能出現(xiàn)在兩個或兩個以上的雙連分量中。因此，圖 G的雙連分量劃分 E(G)。 圖 G的雙連分量可利用 G的任何深度優(yōu)先生成樹求得。 JYP 8 圖 G6的以頂點 0為根的深度優(yōu)先生成樹如下： JYP 9 其中，非樹邊用虛線表示。頂點旁的數(shù)字稱為該頂點的 深度優(yōu)先數(shù) ，簡稱為 dfn。一個頂點的 dfn表示該頂點在深度優(yōu)先搜索中被訪問的順序。 例如，在前面的 G6生成樹中， dfn(0) = 1， dfn(1) = 2，以及 dfn(7) = 5。 注意，在深度優(yōu)先生成樹中，如果頂點 u是 v的祖先，則 dfn(u) dfn(v)。 JYP 10 相對于生成樹 T， 當且僅當 u是 v的祖先或 v是 u的祖先時 ， 非樹邊 (u, v) 才是一條 回邊 。 例如 ， (4, 1) 和 (6, 7) 是回邊 。 不是回邊的非樹邊稱為 橫邊 。 根據(jù)深度優(yōu)先搜索的規(guī)律 ， 相對于任意一個圖的任何深度優(yōu)先生成樹 ，該圖不可能有橫邊 。 JYP 11 因此 ， 深度優(yōu)先生成樹的根是關節(jié)點的充分必要條件是它至少有兩個子女 。 任何其它頂點 u是關節(jié)點的充分必要條件是 u至少有一個子女 w， 使得經(jīng)過只由 w， w的后代以及一條回邊構成的路徑不可能到達 u的祖先 ， 因為刪除頂點 u及其關聯(lián)的邊將使 w及其后代與 u的祖先斷開聯(lián)系 。 JYP 12 假設頂點 w的祖先包括 w本身。 為了表示一個頂點經(jīng)過其后代以及一條回邊所能到達的最高祖先，對于圖 G的每個頂點 w，定義low(w) 為從 w經(jīng)過其后代以及一條回邊所能到達的最高祖先的 dfn。 顯然， low(w)是從 w經(jīng)過其后代以及一條回邊所能到達的頂點的 dfn中最低的，并可由以下公式計算： low(w) = min {dfn(w), min {low(x)| x是 w的一個子女 }, min {dfn(x)| (w, x) 是一條回邊 }} JYP 13 于是， u是關節(jié)點的充分必要條件是： u或者是至少有兩個子女的深度優(yōu)先生成樹的根，或者 u不是根結點但有一個子女 w，使得 low(w)≥dfn(u)。 下面是 G6的以頂點 0為根的深度優(yōu)先生成樹中各頂點的 dfn和 low值： 頂點 0 1 2 3 4 5 6 7 dfn 1 2 7 3 4 6 8 5 low 1 2 5 2 2 5 5 5 JYP 14 修改 DFS可得到計算一個連通圖各頂點的 dfn和low值的函數(shù) DfnLow： void Graph::DfnLow (const int x ) { // 在頂點 x開始 DFS num = 1。 // num是 Graph 的類型為 int的數(shù)據(jù)成員 dfn = new int[n]。 low = new int[n]。 // dfn和 low都是 Graph 的 // 類型為 int *的數(shù)據(jù)成員 for ( int i = 0。 i n。 i++ ) { dfn[i] = low[i] = 0。 } DfnLow ( x, 1 )。 // x是根，其雙親是偽頂點 1 delete [ ] dfn。 delete [ ] low。 } JYP 15 void Graph::DfnLow ( int u, int v ) { // 從 u開始深度優(yōu)先搜索并 // 計算 dfn和 low。 v是 u的雙親 dfn[u] = low[u] = num++。 for (每一個與 u鄰接的頂點 w) // 具體代碼與圖的表示有關 if (dfn[w] == 0) { // w 是未被訪問頂點 DfnLow (w, u)。 low[u] = min2 (low[u], low[w])。 // min2(x,y)返回 x和 y的 // 較小者 } else if (w != v) low[u] = min2 ( low[u], dfn[w] )。 // 回邊。注 // 意 (v, u)不是回邊 } JYP 16 注意 ， 在深度優(yōu)先生成樹中 ， 若 v是 u的雙親 ， 則 (u, v) 一定不是回邊 。 函數(shù) DfnLow(u, v)的參數(shù) v就是為區(qū)分這種情況而設的 。 深度優(yōu)先搜索的第一個頂點 x無雙親 ， 因此對其的調(diào)用形式為 DfnLow(x, –1)。 函數(shù) DfnLow(u, v)用到的另一個函數(shù) min2返回其兩個參數(shù)的較小者 。 JYP 17 在 DfnLow的基礎上進一步處理 ， 可以將連通圖的邊劃分為雙連分量 。 注意 ， 當 DfnLow(w, u)返回后 ， low[w]已計算好 。如果 low[w]≥dfn[u]， 則可確定一個新的雙連分量 。 通過將搜索時首次遇到的邊存入棧中 ， 可以求得一個雙連分量的全部邊 。 JYP 18 設深度優(yōu)先搜索最近訪問的頂點是 u， 且頂點 w與 u鄰接但不是 u的直接雙親 ， 則在以下兩種情況中 ，(u, w)是首次遇到的邊： （ 1） w是未被訪問的頂點 （ 2） w是已被訪問的頂點而且是 u的祖先 由于未被訪問的頂點的 dfn值初始化為 0， 祖先的dfn值小于后代的 ， 所以兩種情況都可歸結為 dfn[w] dfn[u]。 JYP 19 注意：如果 dfn[w] dfn[u]， 則邊 （ w， u） 一定已經(jīng)作為回邊 （ 當處于 w點時 ） 加到棧中 ， 如下所示： u x w 2 3 4 JYP 20 函數(shù) Biconnected實現(xiàn)了上述過程： void Graph::Biconnected ( ) { num = 1。 dfn = new int[n]。 low = new int[n]。 for ( int i = 0。 i n。 i++ ) { dfn[i] = low[i] = 0。 } Biconnected (0, 1)。 // 從頂點 0開始 delete [ ] dfn。 delete [ ] low。 } void Graph::Biconnected (int u, int v) { // 計算 dfn和 low，并輸 // 出各雙連分量的邊。 v是 u 的雙親，棧 S是 Graph的數(shù) // 據(jù)成員，并被初始化為空。假設 n1。 dfn[u] = low[u] = num++。 JYP 21 for (每一個與 u鄰接的頂點 w) { // 具體代碼與圖的表示有關 if (v != w amp。amp。 dfn[w] dfn[u]) 將邊 (u,w) 加入棧 S中 。 if (dfn[w] == 0 ) { // w是未被訪問的頂點 Biconnected (w, u)。 low[u] = min2 (low[u], low[w])。 if (low[w] = dfn[u]) { cout “新雙連分量：” endl。 do { 從棧 S刪除一條邊 。 設此邊為 (x, y)。 cout x , y endl。 } while ( (x, y)與 (u, w)不相同 )。 } } else if (w != v) low[u] = min2 (low[u], dfn[w])。 // 回邊 } // for結束 } JYP 22 Biconnected的時間復雜性是 O(n + e)。 注意 ， 函數(shù) Biconnected假設輸入的連通圖至少有兩個頂點 。 只有一個頂點的連通圖無邊 ， 但按定義 ， 它們也是雙連通的 。 對此可作特殊處理 。 JYP 23 求解最小生成樹的 普瑞姆算法 （ ） 設 TV是最小生成樹的已選頂點集合 ， T是最小生成樹的已選邊集合 。 普瑞姆算法首先任選圖 G中一個頂點 u， 將 u加入 TV中 。 然后將一條代價最小的邊 (u, v) 加入 T中 ， 使得 T ? {(u, v)}仍然是一棵樹 。 重復上述步驟 ， 直到 T包含 n – 1條邊為止 。 注意 ， (u, v) 關聯(lián)的兩個頂點必有一個在 TV中 ，另一個不在 TV中 。 JYP 24 普瑞姆算法的框架 : TV = {0}。 // 從頂點 0開始構造，假設 G至少有一個頂點 for ((T = ?。 T包含的邊少于 n 1條 。 將 (u, v)加入 T) { 令 (u, v) 為滿足 u ? TV 且 v ? TV 的代價最小的邊 。 if (不存在這樣的邊 ) break。 將 v加入 TV。 } if (T包含的邊少于 n1條 ) cout “不存在最小生成樹” endl 。 JYP 25 用普瑞姆算法構造下圖的最小生成樹的過程： JYP 26 JYP 27 JYP 28 JYP 29 設 是不屬于 TV的頂點集合。 對于任何 v? ，定義 near[v]為 TV中使 cost(near[v], v)最小的頂點（若 (v, w)?E，則設cost(v, w) = ?），則 cost(near[v],v) = 。 下一個加入 TV的頂點 v應滿足： v? ，且cost(near[v],v) = 。下一條加入 T的邊自然是 (near[v],v)。 TVTV)},({ c o sm i n vutTVu ?TV)}],[({ c o sm i n xxn e a rtTVx ?JYP 30 設 w是 中與 v鄰接的頂點。頂點 v加入 TV之后，如果 cost(near[w],w) cost(v, w)，則將 near[w]改為v。 由此可以有效地實現(xiàn)普瑞姆算法。 如果用鄰接矩陣 cost[i][j]表示圖 G，則算法的時間復雜性是 O(n2)，因為算法總共選 n – 1個頂點，每選一個頂點 v及處理 v對 near[w]（ w? 且 w與 v鄰接）的影響最多只需 O(n)時間。 TVTVJYP 31 如果用鄰接表表示圖 G并利用斐波納契堆 ， 則可使算法的性能更好 。 對于 v? ， 定義 dist[v] = cost(near[v],v)， 可理解為頂點 v到已構造的部分最小生成樹的最近距離 。 每次往 TV中加入一個頂點 ， 算法都需要確定頂點 v， 使得 v? ， 且 dist[v] = 。 這對應于 上的刪除最小元素操作 。 由于 v加入 TV，