最小生成樹問題

最小生成樹問題1/9/2023賦權(quán)連通圖的最小支撐樹邊的權(quán):G=(V,E)對每邊ei∈E規(guī)定一個(gè)非負(fù)的實(shí)數(shù)w(ei)叫“權(quán)”；帶權(quán)圖:每邊都有權(quán)的圖叫賦權(quán)圖或帶權(quán)圖；樹:其特點(diǎn)之一是邊數(shù)比頂點(diǎn)數(shù)少一；圖G的支撐樹T:E(T)E(G),V(T)=V(G),即由G找T，頂點(diǎn)一個(gè)不能少，邊可能刪去幾條，但T必須是樹[當(dāng)然如G不是連通圖，則沒有支撐樹]。最小樹:賦權(quán)的連通圖G的眾多支撐樹中必至少有一，其各邊權(quán)之和為最小的，它就叫G的一棵最小支撐樹或最小生成樹；簡稱最小樹或最短樹[管線鋪設(shè)]。最小樹的存在性：賦權(quán)的連通圖G=(V,E),記m=|E|,n=|V|,支撐樹T的邊數(shù)|E(T)|=n-1,E(T)必為V的n-1元子集，顯然這種子集合最多個(gè)，所以支撐樹是有限的，其權(quán)組成有限集，必有最小的[但可能不唯一]。

1/9/2023求最小樹的Kruskal算法賦權(quán)的連通圖G=(V,E)中m=|E|,n=|V|,S1:對E中各邊的權(quán)排序，設(shè)w1≤w2≤…≤wm,wi=w(ei)S2:初始化：w←0,T←φ,k←1,t←0S3:若t=n-1則轉(zhuǎn)S6，否則轉(zhuǎn)S4S4:若T∪{ek}有圈則k←k+1轉(zhuǎn)S4，否則轉(zhuǎn)S5S5:T←T∪{ek},w←w+wk,t←t+1,k←k+1,轉(zhuǎn)S3S6:輸出T及w，結(jié)束。T為最小樹，w為T的權(quán)。這個(gè)算法叫Kruskal算法(避圈法)T’←T∪{ek}t=n-1?k←k+1NY輸出T,wENDSTARTE的權(quán)排序w1≤w2≤…≤wmw←0,T←φ,k←1,t←0T’成圈?YNT←T+{ek},w←w+wk,t←t+1,k←k+11/9/2023用Kruskal算法求最小樹用Kruskal算法(避圈法)求賦權(quán)連通圖G的最小樹V1V2V3V5V4V6V723798105612445611723644565∴最小樹的權(quán)為24，最小樹為T={v1v2,v1v3,v2v5,v5v6,v6v7,v6v4}1/9/2023避圈法求最小樹的分析Kruskal算法的“主要”工作如認(rèn)為是[S1:]

對m條邊的邊長排序，m個(gè)元素排序較好的算法是基于分治策略的快速排序(QuickSorting)，其時(shí)間復(fù)雜性是O(m㏒m)。快速排序算法： 找一個(gè)數(shù)如第一個(gè)k，待排序的數(shù)可以分為大于k的和小于k的兩部分，分別對這兩部分繼續(xù)用快速排序[遞歸]，最后合并聯(lián)接就可以了。說明： “是否成圈”的判斷事實(shí)上不比邊長排序來得容易，尤其是用計(jì)算機(jī)程序?qū)崿F(xiàn)時(shí)。要讓程序讀懂“圖”，程序如何判斷是否成“圈”？談何容易，時(shí)間、空間復(fù)雜性絕不應(yīng)小看1/9/2023Prim法求最小支撐樹Kruskal法盯住邊,而Prim法更注意頂點(diǎn):從任一頂點(diǎn)開始都可以,逐個(gè)把最近的頂點(diǎn)找進(jìn)來(找過的不找,就不會成圈)。算法如下:S1:T←{v1},S←V\{v1},w←0S2:若S=φ轉(zhuǎn)S5,否則轉(zhuǎn)S3S3:S4:T←T∪{vk},S←S\{vk},w←w+w(vlvk),轉(zhuǎn)S2S5:輸出T及w,停止.1/9/2023用Prim算法(就近法)求賦權(quán)連通圖G的最小樹V1V2V3V5V4V6V7237981056124456117236445∴最小樹的權(quán)為24，最小樹為Tree={v1v2,v1v3,v2v5,v5v6,v6v7,v6v4}T={v1}S={v2,v3,v4,v5,v6,v7}T={v1,v2}T={v1,