【正文】 的造價是不一樣的，那么如何設計才能使得總造價最小？ 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 MST性質(zhì) 假設 G=(V, E)是一個無向連通網(wǎng) ， U是頂點集 V的一個非空子集 。 若 (u, v)是一條具有最小權值的邊 ， 其中 u∈ U， v∈ V－ U， 則必存在一棵包含邊 (u, v)的最小生成樹 。 頂點集U V－ U u39。 v v39。 u 頂點集 T1 T2 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 基本思想 ：設 G=(V, E)是具有 n個頂點的連通網(wǎng) ，T=(U, TE)是 G的最小生成樹 ， T的 初始狀態(tài) 為U={u0}（ u0∈ V） ， TE={ }， 重復執(zhí)行下述操作：在所有 u∈ U， v∈ VU的邊中找一條代價最小的邊(u, v)并入集合 TE， 同時 v并入 U， 直至 U=V。 關鍵 :是如何找到連接 U和 VU的最短邊 。 1. 普里姆（ Prim） 算法 利用 MST性質(zhì)，可以用下述方法構造候選最短邊集：對應 VU中的每個頂點，保留從該頂點到 U中的各頂點的最短邊。 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 U={A} VU={B, C, D, E, F} cost={(A, B)34, (A, C)46, (A, D)∞,(A, E)∞,(A, F)19} 25 12 34 19 26 46 38 17 25 A B E D C F Prim算法 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 Prim算法 25 12 34 19 26 46 38 17 25 A B E D C F U={A, F} VU={B, C, D, E} cost={(A, B)34,(F, C)25, (F, D)25,(F, E)26} 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 Prim算法 25 12 34 19 26 46 38 17 25 A B E D C F U={A, F, C} VU={B, D, E} cost={(A, B)34, (C, D)17, (F, E)26} 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 Prim算法 25 12 34 19 26 46 38 17 25 A B E D C F U={A, F, C, D} VU={B, E} cost={(A, B)34, (F, E)26} 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 Prim算法 25 12 34 19 26 46 38 17 25 A B E D C F U={A, F, C, D, E} VU={B} cost={(E, B)12} 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 Prim算法 25 12 34 19 26 46 38 17 25 A B E D C F U={A, F, C, D, E, B} VU={ } 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 設置一個輔助數(shù)組，對當前 V－ U集中的每個頂點，記錄和頂點集 U中頂點相連接的代價最小的邊： struct { VertexType adjvex。 // U集中的頂點序號 VRType lowcost。 // 邊的權值 } closedge[N]。 表示頂點 vi和頂點 vk之間的權值為 w，其中： vi∈ VU 且 vk ∈ U lowcost[i]=w adjvex[i]=k 如何用數(shù)組 lowcost和 adjvex表示候選最短邊集？ 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 cl o s ed g e0 1 2 3 4 5 6A d j v exL o w cos ta a a 19 14 18 例如 : e12 e e8 16 d 3 d d 7 21 c5 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 void MiniSpanTree_P(MGraph G, VertexType u) { //用普里姆算法從頂點 u出發(fā)構造網(wǎng) G的最小生成樹 k = LocateVex ( G, u )。 for ( j=0。 j。 ++j ) // 輔助數(shù)組初始化 if (j!=k) closedge[j] = { u, [k][j].adj }。 closedge[k].lowcost = 0。 // 初始， U＝ {u} for (i=0。 i。 ++i) { } 繼續(xù)向生成樹上添加頂點 。 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 k = minimum(closedge)。 // 求出加入生成樹的下一個頂點 (k) printf(closedge[k].adjvex, [k])。 // 輸出生成樹上一條邊 closedge[k].lowcost = 0。 // 第 k頂點并入 U集 for (j=0。 j。 ++j) //修改其它頂點的最小邊 if ([k][j].adj closedge[j].lowcost) closedge[j] = { [k], [k][j].adj }。 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 2. 克魯斯卡爾（ Kruskal）算法 基本思想 ：設無向連通網(wǎng)為 G＝ (V, E)， 令 G的最小生成樹為 T＝ (U, TE)， 其 初態(tài)為 U＝ V， TE＝ { }， 然后 ，按照 邊的權值由小到大的順序 ， 考察 G的邊集 E中的各條邊 。 若被考察的邊的兩個頂點屬于 T的兩個不同的 連通分量 ， 則將此邊作為最小生成樹的邊加入到 T中 ， 同時把兩個連通分量連接為一個連通分量；若被考察邊的兩個頂點屬于同一個連通分量 ， 則舍去此邊 ， 以免造成回路 ， 如此下去 ， 當 T中的連通分量個數(shù)為 1時 ，此連通分量便為 G的一棵最小生成樹 。 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 25 12 34 17 26 46 38 19 25 A B E D C F A B E D C F 連通分量＝ {A}, {B}, {C}, {D}, {E}, {F} 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 25 12 34 17 26 46 38 19 25 A B E D C F A B E D C F 連通分量＝ {A}, {B}, {C}, {D}, {E}, {F} 12 連通分量＝ {A}, {B, E}, {C}, {D}, {F} 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 25 12 34 17 26 46 38 19 25 A B E D C F A B E D C F 連通分量＝ {A}, {B, E}, {C}, {D}, {F} 12 連通分量＝ {A, F}, {B, E}, {C}, {D} 17 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 25 12 34 17 26 46 38 19 25 A B E D C F A B E D C F 連通分量＝ {A, F}, {B, E}, {C}, {D} 12 連通分量＝ {A, F}, {B, E}, {C, D} 17 19 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 25 12 34 17 26 46 38 19 25 A B E D C F A B E D C F 連通分量＝ {A, F}, {B, E}, {C, D} 12 連通分量＝ {A, F, C, D}, {B, E} 17 19 25 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 25 12 34 17 26 46 38 19 25 A B E D C F A B E D C F 連通分量＝ {A, F, C, D}, {B, E} 12 連通分量＝ {A, F, C, D, B, E} 17 19 25 26 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 1. 初始化： U=V； TE={ }； 2. 循環(huán)直到 T中的連通分量個數(shù)為 1 在 E中尋找最短邊 (u， v)。 如果頂點 u、 v位于 T的兩個不同連通分量 ， 則 將邊 (u， v)并入 TE； 將這兩個連通分量合為一個； 在 E中標記邊 (u， v)， 使得 (u， v)不參加后續(xù)最短邊的選??； Kruskal算法 ——偽代碼 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 普里姆算法 克魯斯卡爾算法 時間復雜度 O(n2) O(eloge) 稠密圖 稀疏圖 算法名 適應范圍 比較兩種算法 圖的連通性 —— 最小生成樹 數(shù)據(jù)結構（ C版） 清華大學出版社 簡單說：由某集合上的一個偏序得到該集合上的一個全序，這個操作稱為拓撲排序。 直觀地看：偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。 什么是拓撲排序？ 拓撲排序 B D A C C B A D 由偏序定義得到拓撲有序的操作便是拓撲排序。 數(shù)據(jù)結構（ C版） 清華大學出版社 AOV網(wǎng)： 在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系， 稱這樣的有向圖為 頂點表示活動 的網(wǎng)，簡稱 AOV網(wǎng)。 AOV(Activity On Vertex)網(wǎng) 什么是工程？工程有什么共性？ AOV網(wǎng)中出現(xiàn)回路意味著什么？ 拓撲排序 一個表示偏序的有向圖可用來表示流程圖。如施工流圖 數(shù)據(jù)結構（ C版） 清華大學出版社 AOV網(wǎng)： 在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關系， 稱這樣的有向圖為 頂點表示活動 的網(wǎng)，簡稱 AOV網(wǎng)。 AOV網(wǎng) 。 AOV網(wǎng)特點： 。 什么是工程？工程有什么共性？ 拓撲排序 數(shù)據(jù)結構（ C版） 清華大學出版社 編號 課程名稱 先修課 C1 高等數(shù)學 無 C2 計算機導論 無 C3 離散數(shù)學 C1 C4 程序設計 C1, C2 C5 數(shù)據(jù)結構 C3， C4 C6 計算機原理 C2， C4 C7 數(shù)據(jù)庫原理 C4， C5， C6 拓撲排序 C1 C2 C3 C4 C6 C5 C7 AOV網(wǎng) 數(shù)據(jù)結構（ C版） 清華大學出版社 何謂“拓撲排序”？ 對有向圖進行如下操作： 按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系。 拓撲排序 檢查有向圖中是否存在回路的方法之一，是對有向圖進行 拓撲排序 。 數(shù)據(jù)結構（ C版） 清華大學出版社 例如：對于下列有向圖 B D A C 可求得 拓撲有序序列 ： A B C D 或 A C B D 由此所得頂點的線性序列稱之為 拓撲有序序列 拓撲排序 數(shù)據(jù)結構（ C版） 清華大學出版社 B D A C 反之，對于下列有向圖 不能求得它的拓撲有序序列。 因為圖中存在一個回路