【正文】 最近距離 。頂點 v加入 TV之后，如果 cost(near[w],w) cost(v, w)，則將 near[w]改為v。 對于任何 v? ，定義 near[v]為 TV中使 cost(near[v], v)最小的頂點（若 (v, w)?E，則設(shè)cost(v, w) = ?），則 cost(near[v],v) = 。 if (不存在這樣的邊 ) break。 JYP 24 普瑞姆算法的框架 : TV = {0}。 普瑞姆算法首先任選圖 G中一個頂點 u， 將 u加入 TV中 。 注意 ， 函數(shù) Biconnected假設(shè)輸入的連通圖至少有兩個頂點 。 cout x , y endl。 low[u] = min2 (low[u], low[w])。 JYP 21 for (每一個與 u鄰接的頂點 w) { // 具體代碼與圖的表示有關(guān) if (v != w amp。 } void Graph::Biconnected (int u, int v) { // 計算 dfn和 low，并輸 // 出各雙連分量的邊。 i++ ) { dfn[i] = low[i] = 0。 dfn = new int[n]。如果 low[w]≥dfn[u]， 則可確定一個新的雙連分量 。 深度優(yōu)先搜索的第一個頂點 x無雙親 ， 因此對其的調(diào)用形式為 DfnLow(x, –1)。 // min2(x,y)返回 x和 y的 // 較小者 } else if (w != v) low[u] = min2 ( low[u], dfn[w] )。 } JYP 15 void Graph::DfnLow ( int u, int v ) { // 從 u開始深度優(yōu)先搜索并 // 計算 dfn和 low。 i++ ) { dfn[i] = low[i] = 0。 // num是 Graph 的類型為 int的數(shù)據(jù)成員 dfn = new int[n]。 JYP 12 假設(shè)頂點 w的祖先包括 w本身。 不是回邊的非樹邊稱為 橫邊 。 例如，在前面的 G6生成樹中， dfn(0) = 1， dfn(1) = 2，以及 dfn(7) = 5。 圖 G的雙連分量可利用 G的任何深度優(yōu)先生成樹求得。 定義： 一個連通圖 G的 雙連分量 是 G的最大雙連通子圖。 JYP 3 例如 ， 在下面的連通圖 G6中 ， 頂點 1， 4和 7是關(guān)節(jié)點 。JYP 1 高級數(shù)據(jù)結(jié)構(gòu) (下 ) 教材： 《 數(shù)據(jù)結(jié)構(gòu)（ C++描述） 》（金遠(yuǎn)平編著，清華大學(xué)出版社） JYP 2 雙連分量 () 雙連分量在連通性方面比一般的連通分量具有更高的要求，生成雙連分量的操作也更復(fù)雜一些。 JYP 4 定義：雙連通圖 是沒有關(guān)節(jié)點的連通圖。 JYP 6 圖 G6包含四個雙連分量，如下所示： JYP 7 不難發(fā)現(xiàn)，同一個圖的兩個雙連分量最多有一個共同頂點。 JYP 8 圖 G6的以頂點 0為根的深度優(yōu)先生成樹如下： JYP 9 其中，非樹邊用虛線表示。 注意，在深度優(yōu)先生成樹中，如果頂點 u是 v的祖先，則 dfn(u) dfn(v)。 根據(jù)深度優(yōu)先搜索的規(guī)律 ， 相對于任意一個圖的任何深度優(yōu)先生成樹 ，該圖不可能有橫邊 。 為了表示一個頂點經(jīng)過其后代以及一條回邊所能到達(dá)的最高祖先，對于圖 G的每個頂點 w，定義low(w) 為從 w經(jīng)過其后代以及一條回邊所能到達(dá)的最高祖先的 dfn。 low = new int[n]。 } DfnLow ( x, 1 )。 v是 u的雙親 dfn[u] = low[u] = num++。 // 回邊。 函數(shù) DfnLow(u, v)用到的另一個函數(shù) min2返回其兩個參數(shù)的較小者 。 通過將搜索時首次遇到的邊存入棧中 ， 可以求得一個雙連分量的全部邊 。 low = new int[n]。 } Biconnected (0, 1)。 v是 u 的雙親，棧 S是 Graph的數(shù) // 據(jù)成員，并被初始化為空。amp。 if (low[w] = dfn[u]) { cout “新雙連分量：” endl。 } while ( (x, y)與 (u, w)不相同 )。 只有一個頂點的連通圖無邊 ， 但按定義 ， 它們也是雙連通的 。 然后將一條代價最小的邊 (u, v) 加入 T中 ， 使得 T ? {(u, v)}仍然是一棵樹 。 // 從頂點 0開始構(gòu)造，假設(shè) G至少有一個頂點 for ((T = ?。 將 v加入 TV。 下一個加入 TV的頂點 v應(yīng)滿足： v? ，且cost(near[v],v) = 。 由此可以有效地實現(xiàn)普瑞姆算法。 每次往 TV中加入一個頂點 ， 算法都需要確定頂點 v， 使得 v? ， 且 dist[v] = 。 TVTV ]}[{m in xd is tTVx ?TVTVTVJYP 32 關(guān)鍵字減少操作的總次數(shù)最多是圖中邊的條數(shù) 。 接著需要執(zhí)行 n – 1次刪除最小元素操作和最多 e次關(guān)鍵字減少操作 。 TVTVJYP 33 斐波納契堆在 最短路徑算法中的應(yīng)用 先回憶一下經(jīng)典的最短路徑算法： 1 void Graph::ShortestPath(const int n, const int v) { 2 for (int i = 0。 4 if ( i != v amp。 5 } 6 s[v] = TRUE。 i++) { // 確定從 v開始的 n – 1條路徑 8 int u = choose(n)。 w++) 11 if (!s[w]) 12 if (dist[u] + length[u][w] dist[w]) { dist[w] = dist[u] + length[u][w]。第 7行的for循環(huán)執(zhí)行 n – 2次，每次需要 O(n)時間用于第 8行的選擇和第 10到 12行的更新 dist值。 JYP 36 S 應(yīng)用斐波納契堆 和鄰接表，可使算法的時間復(fù)雜性減少為 O(n log n + e)。這對應(yīng)于 上的關(guān)鍵字減少操作。 所有這些操作的代價是各操作的分?jǐn)偞鷥r之和 ，即 O(n log n + e)。 設(shè)記錄表 R0, … , Rn1經(jīng)排序后的結(jié)果是一個按關(guān)鍵字非遞減次序鏈接的鏈表 ， 且 first是鏈表的首記錄指針 。 JYP 39 但在單鏈表中 ， 我們無法快速確定結(jié)點 R0的前驅(qū)Rx。 重復(fù)上述過程 n–1次即可完成重新排列 。 i n – 1。 // list[q]是按非遞減次序的下一個 // 記錄，可能是虛擬記錄 if (first != i) { // 交換 list[i] 和 list[first]，并將 list[i].link // 設(shè)置為原 list[i]的新位置 ElementKeyType t = list[i]。 } first = q。 所以 ，最壞情況下記錄移動的總代價是 O(mn)。 對于這些方法可以采用映射表 t， 表的每一個單元對應(yīng)一個記錄 。 排序結(jié)束時 ，關(guān)鍵字最小的記錄是 Rt[0]， 最大的記錄是 Rt[n1]， 所要求的記錄排列是 Rt[0], Rt[1], … , Rt[n1]， 如下一頁所示 。 例如，上一頁的置換由兩個環(huán)路組成，第一個包含記錄 R0和 R4，第二個包含記錄 R1， R3和 R2。 JYP 52 template class KeyType void table(ElementKeyType *list, const int n, int *t) { // 重新排列 list[0], …, list[n 1]，使其對應(yīng)序列 list[t[0]], …, // list[t[n1]], n≥1 for (int i = 0。 do { int k = t[j]。 } while ( t[j] != i )。 for循環(huán)執(zhí)行了 n–1次。對于平凡環(huán)路，則令 kj = 0。如果不空，該樹應(yīng)滿足以下性質(zhì)： （ 1） 每個元素有一個關(guān)鍵字，且任何兩個不同的元素的關(guān)鍵字不相等（即關(guān)鍵字唯一）； （ 2） 左子樹（如果存在的話）中的關(guān)鍵字小于根結(jié)點中的關(guān)鍵字； （ 3） 右子樹（如果存在的話）中的關(guān)鍵字大于根結(jié)點中的關(guān)鍵字； （ 4） 左、右子樹也是二叉查找樹。最后將 A和 B設(shè)置為空。 JYP 59 （ 3） (i, B, x, C)： 分裂為三部分： B包含 A中所有關(guān)鍵字小于 i的元素；如果 A含關(guān)鍵字為 i的元素，則將該元素復(fù)制到x，并返回 x的指針，否則返回 0； C包含 A中所有關(guān)鍵字大于 i的元素。 計算時間是 O(1)， 新樹 C的高度是 max{height(A), height(B)}+1。 計算時間是 O(height(A))， 新樹 C的高度不超過 max{height(A), height(B)}+1。 如果 i大于根結(jié)點的關(guān)鍵字 ， 根結(jié)點及其左子樹應(yīng)屬于 B， 如圖 （ c） 所示 。 若 i t?， 則結(jié)點 t及其左子樹應(yīng)加入 B中 。 下面是實現(xiàn)分裂操作的算法： template class Type ElementType* BSTType::Split(Type i, BSTTypeamp。 return 0。 // C的頭結(jié)點 BstNodeType *L = Z。 x = t?data。 // 刪除頭結(jié)點 = Z?LeftChild。x。 } JYP 68 } else { R?RightChild = t。 // 注意這是必要的 = Y?RightChild。 // 刪除頭結(jié)點 root = 0。 算法的時間復(fù)雜性是 O(height(A))。 二叉樹原來的 （ 圓 ） 結(jié)點稱為內(nèi)部結(jié)點 。 內(nèi)部路徑長度 I是所有內(nèi)部結(jié)點到根結(jié)點的路徑長度之和。 假設(shè) n = m時引理 。 JYP 74 將 v的兩個子女從樹中刪除，使 v成為新的外部結(jié)點，樹的內(nèi)部結(jié)點個數(shù)減少為 m，內(nèi)部路徑長度減少為 I – k。 JYP 76 1 最壞情況 根據(jù)引理 ，具有最大 I的擴(kuò)展二叉查找樹也具有最大的 E。采用完全二叉樹的結(jié)點編號，結(jié)點 i到根結(jié)點的距離是 ?log2i?。 由于 ln n = (ln 2) (log2n)，所以， Un ? 2 (ln 2) (log2n) ? log2n () ? ?113121 . . . ???? n1113121 ...1 ?????? nnJYP 84 由 ()式， Sn ? log2n – 1。 當(dāng)查找各標(biāo)識符的概率相同時，可以用最好情況二叉查找樹表示該符號表。 設(shè)需要構(gòu)造的二叉查找樹包含標(biāo)識符 a1, a2, …, a n，且 a1 a2 … a n，查找每個 ai,的概率是 pi，則當(dāng)查找只限于成功情況時，該二叉查找樹的代價是 )(1inii al e v e lp ????JYP 87 不成功查找在算法 Search檢查到失敗結(jié)點時結(jié)束 。 將失敗結(jié)點從 0到 n編號 ， 編號 i的失敗結(jié)點對應(yīng) Ei，0≤i≤n。 JYP 93 采用例 雜性很高 。 設(shè) cij為 Tij的代價 。由定義， wii = qi， 0≤i≤n。 根據(jù) ()， Tij的代價 cij = pk+L的代價 +R的代價 +L的權(quán)重 +R的權(quán)重 其中， L