【文章內(nèi)容簡介】 題 ?最小生成樹（ Minimum Cost Spanning Tree） ?問題背景 ?假設(shè)要在 n個城市之間建立通信聯(lián)絡網(wǎng)，則連通 n個城市只需要 n— 1條線路。 ?如何在最節(jié)省經(jīng)費的前提下建立這個通信網(wǎng)。 ?在每兩個城市之間都可以設(shè)置一條線路，相應地都要付出一定的經(jīng)濟代價。 ?n個城市之間，最多可能設(shè)置 n(n1)/2條線路，那么，如何在這些可能的線路中選擇 n1條，以使總的耗費最少呢 ? 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?分析問題（建立模型） ?可以用連通網(wǎng)來表示 n個城市以及 n個城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩城市之間的線路，賦于邊的權(quán)值表示相應的代價。 ?對于 n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網(wǎng)。 ?要選擇這樣一棵生成樹，也就是使總的耗費最少。這個問題就是構(gòu)造連通網(wǎng)的最小代價生成樹 (簡稱為最小生成樹 )的問題。 ?一棵生成樹的代價就是樹上各邊的代價之和。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?背景知識（突破點） —— 構(gòu)造最小生成樹可以有多種算法。其中多數(shù)算法利用了最小生成樹的下列一種簡稱為 MST（ Minimum Spanning Tree）的性質(zhì)： ? 假設(shè) N=(V， {E})是一個連通網(wǎng)， U是頂點集 V的一個非空子集。若 (u， v)是一條具有最小權(quán)值 (代價 )的邊，其中 u ∈U ， v∈V U，則必存在一棵包含邊 (u，v)的最小生成樹。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?MST性質(zhì)的證明（反證法） ?假設(shè)網(wǎng) N的任何一棵最小生成樹都不包含 (u ,v)。 ?設(shè) T是連通網(wǎng)上的一棵最小生成樹，當將邊 (u， v)加入到 T中時，由生成樹的定義， T中必存在一條包含 (u , v)的回路。 ?另一方面，由于 T是生成樹，則在 T上必存在另一條邊 (u’,v’)，其中 u’∈U ， v’∈V U，且 u和 u’之間， v和v’之間均有路徑相通。刪去邊 (u’, v’)，便可消除上述回路，同時得到另一棵生成樹 T。 ?因為 (u， v)的代價不高 (u’， v’)，則 T’的代價亦不高于 T， T’是包含 (u， v)的一棵最小生成樹。由此和假設(shè)矛盾。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?解決方案 ?普里姆 (Prim)算法 ?克魯斯卡爾 (Kruskal)算法 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 ?基本思想： ?從連通網(wǎng)絡 N = { V, E }中的某一頂點 u0 出發(fā) , 選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊 ( u0, v ), 將其頂點加入到生成樹頂點集合 U中。 ?以后每一步從一個頂點在 U 中 ,而另一個頂點不在 U 中的各條邊中選擇權(quán)值最小的邊 (u, v), 把它的頂點加入到集合 U 中。如此繼續(xù)下去 , 直到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合 U 中為止。 ?存儲表示： ?鄰接矩陣 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 25 25 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 原圖 (a) (b) 5 0 4 6 1 3 2 10 (c) (d) (e) 5 0 4 6 1 3 2 10 22 12 5 0 4 6 1 2 10 25 14 22 16 12 3 25 22 12 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 ?以二維數(shù)組表示網(wǎng)的鄰接矩陣，令兩個頂點之間不存在的邊的權(quán)值為機內(nèi)允許的最大值 (INT_MAX)，則普里姆算法如下： ?//記錄從頂點集 U到 V— U的代價最小的邊的輔助數(shù)組定義： struct{ VertexType adjvex； VRType lowcost； }closedge[ MAX_VERTEX_NUM ] void MiniSpanTree_PRIM (MGraph G， VertexType u){ //用普里姆算法從第 u個頂點出發(fā)構(gòu)造網(wǎng) G的最小生成樹 T，輸出 T的各條邊。 k =LocateVex(G， u)； for(j=0； j； ++j) if(j!=k) closedge[j] ={u ,[k][j].adj}。 //{adjvex , lowcost} 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 ?closedge[k].lowcost =0； //初始， U={u} for ( i=1； i； ++i){ //選擇其余 k=minimum(closedge)； printf(closedge[k].adjvex, [k])。//輸出生成樹的邊 closedge[k].lowcost=0。 //第 k頂點并入 U集 for (j=0。 j。 ++j) if ([k][j].adjclosedge[j].lowcost) closedge[j]={[k],[k][j].adj}。 }//for }//MiniSpanTree ?普里姆算法的時間復雜度為 O(n2)，與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求邊 稠密 的網(wǎng)的最小生成樹。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?克魯斯卡爾 (Kruskal)算法 求最小生成樹 ?基本思想： ?假設(shè)連通網(wǎng) N=(V， {E})，則令最小生成樹的初始狀態(tài)為只有 n個頂點而無邊的非連通圖 T=(V， {})，圖中每個頂點自成一個連通分量。 ?在 E中選擇代價最小的邊，若該邊依附的頂點落在 T中不同的連通分量上，則將此邊加入到 T中，否則舍去此邊而選擇下一條代價最小的邊。 ?依次類推，直至于中所有頂點都在同一連通分量上為止。 ?存儲表示： ?利用最小堆 (MinHeap)和并查集 (DisjointSets) 實現(xiàn)。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?克魯斯卡爾 (Kruskal)算法 求最小生成樹 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 5 0 4 6 1 3 2 原圖 (a) (b) 南昌航空大學計算機學院 /軟件學院 第 7章 圖 10 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 14 12 原圖 (c) (d) 5 0 4 6 1 3 2 10 14 16 12 (e) (f) (g) 5 0 4 6 1 3 2 10 14 22 16 12 5 0 4 6 1 2 10 25 14 22 16 12 3 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?普里姆算法與克魯斯卡爾算法 比較 ?普里姆算法的時間復雜度為 O(n2)，與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求邊 稠密 的網(wǎng)的最小生成樹。 ?克魯斯卡爾算法的時間復雜度為 O(eloge)(e為網(wǎng)中邊的數(shù)目 )，因此它相對于普里姆算法而言，適合于求邊 稀疏 的網(wǎng)的最小生成樹。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?重連通分量 (Biconnected Component) ?在無向連通圖 G中 , 當且僅當刪去 G中的頂點 v及所有依附于 v的所有邊后 , 可將圖分割成兩個或兩個以上的連通分量，則稱頂點 v為 關(guān)節(jié)點 。 ?沒有關(guān)節(jié)點的連通圖叫做 重連通圖 。 ?在重連通圖上 , 任何一對頂點之間至少存在有兩條路徑 , 在刪去某個頂點及與該頂點相關(guān)聯(lián)的邊時 , 也不破壞圖的連通性。 ?一個連通圖 G如果不是重連通圖，那么它可以包括幾個重連通分量。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?重連通分量 (Biconnected Component) ?在一個無向連通圖 G中 , 重連通分量 可以利用深度優(yōu)先生成樹找到。 ?在圖中各 頂點旁標明的深度優(yōu)先數(shù) , 給出進行深度優(yōu)先搜索時各頂點訪問的次序。 ?深度優(yōu)先生成樹的根是關(guān)節(jié)點的充要條件是它至少有兩個子女。 ?其它頂點 u 是關(guān)節(jié)點的充要條件是它至少有一個子女 w, 從 w 出發(fā) , 不能通過 w、 w 的子孫及一條回邊所組成的路徑到達 u 的祖先。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 A B C D E F G H I J A B C D E F G H J A B C D E F G H J I I 1 2 3 4 5 6 7 8 9 10 根有兩 個子女 關(guān)節(jié)點 關(guān)節(jié)點 關(guān)節(jié)點 南昌航空大學計算機學院 /軟件學院 第 7章 圖 有向無環(huán)圖及其應用 ?有向無環(huán)圖 (Directed Acycline Graph) ?指一個無環(huán)的有向圖，簡稱 DAG圖。 DAG圖是一類較有向樹更一般的特殊有向圖。 ?有向無環(huán)圖是描述含有公共子式的表達式的有效工具 南昌航空大學計算機學院 /軟件學院 第 7章 圖 有向無環(huán)圖及其應用 ?有向無環(huán)圖 ?表達式： ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 用二叉樹描述表達式 描述表達式的有向無環(huán)圖