最小生成樹問題ppt課件

1、邊的權(quán)邊的權(quán):G=(V,E):G=(V,E)對每邊對每邊eiEeiE規(guī)定一個非負的實數(shù)規(guī)定一個非負的實數(shù)w(ei)w(ei)叫叫“權(quán)權(quán)”；帶權(quán)圖帶權(quán)圖: :每邊都有權(quán)的圖叫賦權(quán)圖或帶權(quán)圖；每邊都有權(quán)的圖叫賦權(quán)圖或帶權(quán)圖；樹樹: :其特點之一是邊數(shù)比頂點數(shù)少一；其特點之一是邊數(shù)比頂點數(shù)少一；圖圖G G的支撐樹的支撐樹T:E(T)T:E(T)E(G),V(T)=V(G),E(G),V(T)=V(G),即由即由G G找找T T，頂點一個不能少，頂點一個不能少，邊可能刪去幾條，但邊可能刪去幾條，但T T必須是樹必須是樹 當(dāng)然如當(dāng)然如G G不是連通圖，則沒有支撐樹不是連通圖，則沒有支撐樹 。最小樹最小樹

2、: :賦權(quán)的連通圖賦權(quán)的連通圖G G的眾多支撐樹中必至少有一，其各邊權(quán)之和為的眾多支撐樹中必至少有一，其各邊權(quán)之和為最小的，它就叫最小的，它就叫G G的一棵最小支撐樹或最小生成樹；簡稱最小樹或最短的一棵最小支撐樹或最小生成樹；簡稱最小樹或最短樹樹 管線鋪設(shè)管線鋪設(shè) 。最小樹的存在性：賦權(quán)的連通圖最小樹的存在性：賦權(quán)的連通圖G =(V,E),G =(V,E),記記m=|E|, n=|V|,m=|E|, n=|V|,支撐樹支撐樹T T的的邊數(shù)邊數(shù)|E(T)|=n-1,E(T)|E(T)|=n-1,E(T)必為必為V V的的n-1n-1元子集，顯然這種子集合最多元子集，顯然這種子集合最多 個，所以支

3、撐樹是有限的，其權(quán)組成有限集，必有最小的個，所以支撐樹是有限的，其權(quán)組成有限集，必有最小的 但可能不唯但可能不唯一一 。 1nmC賦權(quán)的連通圖賦權(quán)的連通圖G=(V,E)G=(V,E)中中m=|E|,n=|V|, m=|E|,n=|V|, S1:S1:對對E E中各邊的權(quán)排序，設(shè)中各邊的權(quán)排序，設(shè)w1w2wm,wi=w(ei)w1w2wm,wi=w(ei)S2:S2:初始化：初始化：w0,T,k1,t0w0,T,k1,t0S3:S3:若若t=n-1t=n-1則轉(zhuǎn)則轉(zhuǎn)S6S6，否則轉(zhuǎn)，否則轉(zhuǎn)S4S4S4:S4:若若TekTek有圈則有圈則kk+1kk+1轉(zhuǎn)轉(zhuǎn)S4S4，否則轉(zhuǎn)否則轉(zhuǎn)S5S5S5: T

4、Tek,ww+wk,S5: TTek,ww+wk, tt+1, kk+1, tt+1, kk+1,轉(zhuǎn)轉(zhuǎn)S3S3S6:S6:輸出輸出T T及及w w，終了。，終了。T T為最小樹，為最小樹，w w為為T T的權(quán)。這個算的權(quán)。這個算法叫法叫KruskalKruskal算法算法( (避圈法避圈法) )TTekt=n-1?kk+1NY輸出輸出T,wENDSTARTE的權(quán)排序的權(quán)排序w1w2wmw0,T,k1,t0T成圈?YNTT+ ek, ww+wk, tt+1,kk+1用用KruskalKruskal算法算法( (避圈法避圈法) )求賦權(quán)連通圖求賦權(quán)連通圖G G的最小樹的最小樹V1V2V3V5V4V

5、6V723798105612445611723644565最小樹的權(quán)為最小樹的權(quán)為24，最小樹為，最小樹為T=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4KruskalKruskal算法的算法的“主要工作如認為是主要工作如認為是S1:S1:對對m m條邊的邊長排序，條邊的邊長排序，m m個元素排序較好的算法是基于分治個元素排序較好的算法是基于分治策略的快速排序策略的快速排序(Quick Sorting)(Quick Sorting)，其時間復(fù)雜性是，其時間復(fù)雜性是O(mO(mm)m)。快速排序算法：快速排序算法：找一個數(shù)如第一個找一個數(shù)如第一個k k，待排序的數(shù)可以分為大于，待排

6、序的數(shù)可以分為大于k k的和小于的和小于k k的兩部分，分別對這兩部分繼續(xù)用快速排序的兩部分，分別對這兩部分繼續(xù)用快速排序 遞歸遞歸 ，最，最后合并聯(lián)接就可以了。后合并聯(lián)接就可以了。闡明：闡明：“是否成圈的判斷事實上不比邊長排序來得容易，尤其是否成圈的判斷事實上不比邊長排序來得容易，尤其是用計算機程序?qū)崿F(xiàn)時。要讓程序讀懂是用計算機程序?qū)崿F(xiàn)時。要讓程序讀懂“圖圖”，程序如何，程序如何判斷是否成判斷是否成“圈圈”？談何容易，時間、空間復(fù)雜性絕不應(yīng)？談何容易，時間、空間復(fù)雜性絕不應(yīng)小看小看KruskalKruskal法盯住邊法盯住邊, ,而而PrimPrim法更注意頂點法更注意頂點: :從任一頂點開始都可以從任一頂點開始都可以, ,逐個把最近的頂點找進來逐個把最近的頂點找進來( (找過的不找找過的不找, ,就不會成圈就不會成圈) )。算法如下算法如下: :S1:Tv1, SVv1, w0S1:Tv1, SVv1, w0S2:S2:若若S=S=轉(zhuǎn)轉(zhuǎn)S5,S5,否則轉(zhuǎn)否則轉(zhuǎn)S3S3S3:S3:S4:TTvk,SSvk,ww+w(vlvk),S4:TTvk,SSvk,ww+w(vlvk),轉(zhuǎn)轉(zhuǎn)S2S2S5:S5:輸出輸出T T及及w,w,停頓停頓. .)vv(w)vv(wmin:kljiTvSvji設(shè)用用PrimPrim算法算法( (就近法就近法) )求賦權(quán)連通圖求賦權(quán)連