最小生成樹問題說課講解

最小生成樹問題9/26/2024賦權(quán)連通圖的最小支撐樹邊的權(quán):G=(V,E)對每邊ei∈E規(guī)定一個非負的實數(shù)w(ei)叫“權(quán)”；帶權(quán)圖:每邊都有權(quán)的圖叫賦權(quán)圖或帶權(quán)圖；樹:其特點之一是邊數(shù)比頂點數(shù)少一；圖G的支撐樹T:E(T)

E(G),V(T)=V(G),即由G找T，頂點一個不能少，邊可能刪去幾條，但T必須是樹[當然如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元子集，顯然這種子集合最多個，所以支撐樹是有限的，其權(quán)組成有限集，必有最小的[但可能不唯一]。

9/26/2024求最小樹的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)。這個算法叫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+19/26/2024用Kruskal算法求最小樹用Kruskal算法(避圈法)求賦權(quán)連通圖G的最小樹V1V2V3V5V4V6V723798105612445611723644565∴最小樹的權(quán)為24，最小樹為T={v1v2,v1v3,v2v5,v5v6,v6v7,v6v4}9/26/2024Prim法求最小支撐樹Kruskal法盯住邊,而Prim法更注意頂點:從任一頂點開始都可以,逐個把最近的頂點找進來(找過的不找,就不會成圈)。算法如下: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,停止.9/26/2024用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,v2,v3}T={v1,v2,v3,v