最小樹(shù)問(wèn)題課件

第二節(jié)最小樹(shù)問(wèn)題

一、樹(shù)的基本概念

在各種各樣的圖中，有一類圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖，這就是樹(shù)。

例3已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。如果用六個(gè)點(diǎn)v1…v6代表這六個(gè)城市，在任意兩個(gè)城市之間架設(shè)電話線，即在相應(yīng)的兩個(gè)點(diǎn)之間連一條邊。這樣，六個(gè)城市的一個(gè)電話網(wǎng)就作成一個(gè)圖。任意兩個(gè)城市之間均可以通話，這個(gè)圖必須是連通圖。并且，這個(gè)圖必須是無(wú)圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個(gè)城市的一個(gè)電話網(wǎng)。圖5-6是一個(gè)不含圈的連通圖，代表了一個(gè)電話線網(wǎng)。一、樹(shù)的基本概念

圖5-6v6v3v4v2v5v1一、樹(shù)的基本概念

無(wú)圈且連通的無(wú)向圖稱為樹(shù)．樹(shù)一般記為T(mén)．作為樹(shù)定義還可以有以下幾種表述：

(1)T連通且無(wú)圈或回路；(2)T無(wú)圈且有n－1條邊（如果有n個(gè)結(jié)點(diǎn)）；(3)T連通有n－1條邊；(4)T無(wú)回路，但不相鄰的兩個(gè)結(jié)點(diǎn)之間聯(lián)以一邊，恰得一個(gè)圈；(5)T連通，但去掉T的任意一條邊，T就不連通了；（亦即，在點(diǎn)集合相同的圖中，樹(shù)是含邊數(shù)最少的連通圖。）(6)T的任意兩個(gè)結(jié)點(diǎn)之間恰有一條初等鏈．

1．樹(shù)一、樹(shù)的基本概念

定義3

設(shè)圖K=(V,EI)是圖G=(V,E)的一支撐子圖,如果圖K=(V,EI)是一個(gè)樹(shù),那么稱K是G的一個(gè)支撐樹(shù)或生成樹(shù)。

例如,圖5-7b是圖5-7a的一個(gè)支撐樹(shù)。圖5-7v6v5v2v3v4v1a2.支撐樹(shù)v6v5v2v3v4v1b證明:必要性顯然；充分性:設(shè)圖G是連通的，若G不含圈，則按照定義，G是一個(gè)樹(shù)，從而G是自身的一個(gè)支撐樹(shù)。若G含圈，則任取G的一個(gè)圈，從該圈中任意去掉一條邊，得到圖G的一支撐子圖G1。若G1不含圈，則G1是G的一個(gè)支撐樹(shù)。若G1仍然含圈，則任取G1的一個(gè)圈，再?gòu)娜χ腥我馊サ粢粭l邊，得到圖G的一支撐子圖G2。依此類推，可以得到圖G的一個(gè)支撐子圖GK，且不含圈，從而GK是一個(gè)支撐樹(shù)。定理3一個(gè)圖G有支撐樹(shù)的充要條件是G是連通圖。2.支撐樹(shù)尋找連通圖支撐樹(shù)的方法有“破圈法”。就是從圖中任取一個(gè)圈，去掉一條邊。再對(duì)剩下的圖重復(fù)以上步驟，直到不含圈時(shí)為止，這樣就得到一個(gè)支撐樹(shù)。例4用破圈法求出下圖的一個(gè)支撐樹(shù)。v5v4v2v3v1e6e5e4e3e2e1e7e8取一個(gè)圈(v1,v2,v3,v1)，在一個(gè)圈中去掉邊e3

。在剩下的圖中，再取一個(gè)圈（v1,v2,v4,v3,v1），去掉邊e4

。再?gòu)娜Γ╲3,v4,v5,v3）中去掉邊e6

。再?gòu)娜?v1,v2,v5,v4,v3,v1）中去掉邊e7，這樣，剩下的圖不含圈，于是得到一個(gè)支撐樹(shù)，如圖所示。2.支撐樹(shù)v5v4v2v3v1e6e5e4e3e2e1e7e8v2e1e2e5e8v1v3v4v5破圈法任取一圈，從該圈中去掉任一條邊對(duì)余下的圈重復(fù)相同的步驟直到將圖中所有的圈都破掉為止避圈法也稱為生長(zhǎng)法從圖中某一點(diǎn)開(kāi)始生長(zhǎng)邊逐步擴(kuò)展成長(zhǎng)為一棵樹(shù)每步選取與已入樹(shù)的邊不構(gòu)成圈的那些邊1．最小生成樹(shù)二、最小生成樹(shù)及其算法一個(gè)網(wǎng)絡(luò)圖可以有多個(gè)生成樹(shù)．記N的所有生成樹(shù)的集合為：

T＝{Tk|k＝1，2，…，L

}

設(shè)Tk

＝（V，Ek）是網(wǎng)絡(luò)圖N＝（G，w）的一棵生成樹(shù)，則邊集Ek中所有邊的權(quán)數(shù)之和稱為樹(shù)Tk的權(quán)數(shù)，記為則稱T*為網(wǎng)絡(luò)N的一棵最小生成樹(shù)，簡(jiǎn)稱最小樹(shù)．a(chǎn)bfdec224256345最小樹(shù)比如，城市間交通線的建造等，可以歸結(jié)為這一類問(wèn)題。再如前面例3，在已知的幾個(gè)城市之間聯(lián)結(jié)電話線網(wǎng)，要求總長(zhǎng)度最短和總建設(shè)費(fèi)用最少，這類問(wèn)題的解決都可以歸結(jié)為最小樹(shù)問(wèn)題。1．最小生成樹(shù)(1)避圈法：從網(wǎng)絡(luò)圖中任意節(jié)點(diǎn)開(kāi)始尋找與該節(jié)點(diǎn)關(guān)聯(lián)的權(quán)數(shù)最小的邊，使之與已選邊不構(gòu)成為圈，直到選夠n-1條邊為止。例最小樹(shù)，權(quán)為13v14v21v31231v84v04v45245v73v62v515從網(wǎng)絡(luò)中任選一點(diǎn)

2．最小樹(shù)的求法求最小樹(shù)的兩種方法，是避圈法與破圈法v14v21v31231v84v04v45245v73v62v515(2)破圈法：①在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最短樹(shù)或網(wǎng)絡(luò)不存在最短樹(shù)；②去掉該圈中權(quán)數(shù)最大的邊；反復(fù)重復(fù)①②兩步，直到最小樹(shù)。2．最小樹(shù)的求法（3）Kruskal

算法：將圖中所有邊按權(quán)值從小到大排列，依次選所剩最小的邊加入邊集T，只要不和前面加入的邊構(gòu)成回路，直到T中有n1條邊，則T是最小生成樹(shù)v14v21v31231v84v04v45245v73v62v515圖的矩陣表示將圖的幾何形狀轉(zhuǎn)化為代數(shù)矩陣形式，可大大方便計(jì)算機(jī)對(duì)圖的處理與運(yùn)算。1、無(wú)權(quán)圖的矩陣表示：V5V4V3V2V1V1V2V3V4V5

V101100V210011V310001V401001V501110兩頂點(diǎn)間有邊連接的記為1，無(wú)邊連接的記為0。得到的矩陣一定是對(duì)稱矩陣。2、賦權(quán)無(wú)向圖的矩陣表示：兩頂點(diǎn)間有邊連接的記為該邊的權(quán)數(shù)。無(wú)邊相連的記為，對(duì)角線上的數(shù)是0。得到的矩陣也是對(duì)稱矩陣。例如：V1V2V3V4V5

V1032V23054V3208V4502V54820V5V4V38V25V123423、賦權(quán)有向圖的矩陣表示：左邊的第一列為弧的起點(diǎn)，在每一行中，以該點(diǎn)為起點(diǎn)，按弧的方向，依次填上到各點(diǎn)的權(quán)數(shù)。如沒(méi)有到該點(diǎn)的弧，記為，對(duì)角線上的數(shù)是0。這樣得到的矩陣不一定是對(duì)稱矩陣。例如：起點(diǎn)V1V2V3V4V5

V1032V2054V3608V402V50終點(diǎn)V5V4V38V25V123426（4）Prim算法：不需要對(duì)邊權(quán)排序，即可以直接在網(wǎng)路圖上操作，也可以在邊權(quán)矩陣上操作，后者適合計(jì)算機(jī)運(yùn)算

邊權(quán)矩陣上的Prim算法：1、根據(jù)網(wǎng)路寫(xiě)出邊權(quán)矩陣，兩點(diǎn)間若沒(méi)有邊，則用表示；2、從v1開(kāi)始標(biāo)記，在第一行打，劃去第一列；3、從所有打的行中找出尚未劃掉的最小元素，對(duì)該元素畫(huà)圈，劃掉該元素所在列，與該列數(shù)對(duì)應(yīng)的行打；4、若所有列都劃掉，則已找到最小生成樹(shù)(所有畫(huà)圈元素所對(duì)應(yīng)的邊)；否則，返回第3步。該算法中，打行對(duì)應(yīng)的節(jié)點(diǎn)在V1中，未劃去的列在V2中

最小生成樹(shù)Prim算法是多項(xiàng)式算法Prim算法可以求最大生成樹(shù)網(wǎng)路的邊權(quán)可以有多種解釋，如效率次數(shù)受限的最小生成樹(shù)—尚無(wú)有效算法最小Steiner樹(shù)—尚無(wú)有效算法練習(xí)如圖S,A,B,C,D,E,T代表村鎮(zhèn),村鎮(zhèn)之間的連線上賦予了權(quán)值(可代表距離,費(fèi)用,流量等)現(xiàn)沿圖中連線架設(shè)電線,使各村鎮(zhèn)全部通電,問(wèn)如何架設(shè)使電線總長(zhǎng)最短.(該圖稱為賦權(quán)圖或無(wú)向網(wǎng)絡(luò)).最小生成樹(shù)總長(zhǎng)=2+2+1+3+1+5=14第三節(jié)最短路徑問(wèn)題

最短路徑問(wèn)題是圖論中十分重要的最優(yōu)化問(wèn)題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問(wèn)題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問(wèn)題。

例5如下圖所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長(zhǎng)度?，F(xiàn)在有一個(gè)人要從v1出發(fā)，經(jīng)過(guò)這個(gè)交通網(wǎng)到達(dá)v6，要尋求總路程最短的線路。v6v5v3v1v4v2365112436第三節(jié)最短路徑問(wèn)題

從v1到v6的路線是很多的。比如從v1出發(fā)，經(jīng)過(guò)v2,v4到達(dá)v6或者從v1出發(fā)，經(jīng)過(guò)v2，v3，v5到達(dá)v6等等。但不同的路線，經(jīng)過(guò)的總長(zhǎng)度是不同的。例如，按照第一個(gè)線路，總長(zhǎng)度是3+6+3=12單位，按照第二個(gè)路線，總長(zhǎng)度是3+1+1+6=11單位。第三節(jié)最短路徑問(wèn)題

第三節(jié)最短路徑問(wèn)題

一、基本概念給定一個(gè)賦權(quán)有向圖D＝(V，A),對(duì)每一條弧aij＝w(vi，vj)，相應(yīng)地有權(quán)w(aij)=wij，又有兩點(diǎn)vs、vt∈V,設(shè)p是D中從vs到vt的一條路，路p的權(quán)是p中所有弧的權(quán)之和,記為w(p)．最短路問(wèn)題就是求從vs到vt的路中一條權(quán)最小的路p*:第三節(jié)最短路徑問(wèn)題

下面僅介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法——雙標(biāo)號(hào)法（Dijkstra算法），它是在1959年提出來(lái)的。目前公認(rèn)，在所有的權(quán)wij

≥0時(shí)，這個(gè)算法是尋求最短路問(wèn)題最好的算法。并且，這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。二、最短路問(wèn)題的算法

6.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)計(jì)算兩節(jié)點(diǎn)之間或一個(gè)節(jié)點(diǎn)到所有節(jié)點(diǎn)之間的最短路令dij

表示vi

vj的直接距離(兩點(diǎn)之間有邊)，若兩點(diǎn)之間沒(méi)有邊，則令dij

=，若兩點(diǎn)之間是有向邊，則dji

=；令dii

=0，s表示始點(diǎn)，t表示終點(diǎn)0、令始點(diǎn)Ts=0，并用（）框住，所有其它節(jié)點(diǎn)臨時(shí)標(biāo)記Tj=；1、從vs出發(fā)，對(duì)其相鄰節(jié)點(diǎn)vj1進(jìn)行臨時(shí)標(biāo)記，有Tj1=ds,j1；2、在所有臨時(shí)標(biāo)記中找出最小者，并用框住，設(shè)其為vr。若此時(shí)全部節(jié)點(diǎn)都永久標(biāo)記，算法結(jié)束；否則到下一步；3、從新的永久標(biāo)記節(jié)點(diǎn)vr出發(fā)，對(duì)其相鄰的臨時(shí)標(biāo)記節(jié)點(diǎn)進(jìn)行再標(biāo)記，設(shè)vj2為其相鄰節(jié)點(diǎn)，則Tj2=min{Tj2,Tr+dr,j2}，返回第2步。6.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)計(jì)算兩節(jié)點(diǎn)之間或一個(gè)節(jié)點(diǎn)到所有節(jié)點(diǎn)之間的最短路令dij

表示vi

vj的直接距離(兩點(diǎn)之間有邊)，若兩點(diǎn)之間沒(méi)有邊，則令dij

=，若兩點(diǎn)之間是有向邊，則dji=；令dii

=0，s表示始點(diǎn)，t表示終點(diǎn)對(duì)每個(gè)節(jié)點(diǎn)，用兩種標(biāo)號(hào)：T和P，表示從始點(diǎn)到該節(jié)點(diǎn)的距離，P是最短距離(權(quán))，為永久標(biāo)號(hào)，T是目前路徑的距離，是臨時(shí)標(biāo)號(hào)。通過(guò)不斷改進(jìn)T值，當(dāng)其最小時(shí)，將其改為P標(biāo)號(hào)。開(kāi)始時(shí)，令始點(diǎn)有P=0的P標(biāo)號(hào)，其它節(jié)點(diǎn)為T(mén)=+.標(biāo)號(hào)過(guò)程分為兩步：1.修改T標(biāo)號(hào)。假定是新產(chǎn)生的P標(biāo)號(hào)點(diǎn)，考察以為始點(diǎn)的所有弧段，如果是P標(biāo)號(hào)點(diǎn)，則對(duì)該點(diǎn)不再進(jìn)行標(biāo)號(hào)；如果是T標(biāo)號(hào)點(diǎn)，則進(jìn)行如下修改2.產(chǎn)生新的P標(biāo)號(hào)點(diǎn)，原則：在現(xiàn)有的所有T標(biāo)號(hào)中將值最小者改為P標(biāo)號(hào)二、最短路問(wèn)題的算法

例6求v1到v6的最短路。+∞+∞+∞+∞+∞（1）首先給v1以P標(biāo)號(hào)，P(v1)＝0，給其余所有點(diǎn)T標(biāo)號(hào)，T(vj)＝＋∞（j=2，3，…6)(0)P標(biāo)號(hào)以（）形式標(biāo)在結(jié)點(diǎn)旁邊，T標(biāo)號(hào)以不帶（）的數(shù)字標(biāo)在結(jié)點(diǎn)旁邊.v6v5v3v1v4v2365112436二、最短路問(wèn)題的算法

P(v2)=3

（3）5P(v3)=4

（4）+∞+∞v6v5v3v1v4v2365112436+∞+∞+∞(0)9（2）考察v1:

T(v2)=min[T(v2)，P(v1)+d12]＝min[∞，0＋3]=3T(v3)=min[T(v3)，P(v1)+d13]＝min[∞，0＋5]=5所以，P(v2)=3（3）考察v2:T(v3)=min[T(v3)，P(v2)+d23]＝min[5，3＋1]=4T(v4)=min[T(v4)，P(v2)+d24]＝min[∞，3＋6]=9所以，P(v3)=4T(v3)=5

T(v4)=9

二、最短路問(wèn)題的算法

P(v5)=5（3）（4）v6v5v3v1v4v2365112436+∞+∞(0)9（5）T(v4)=8

（4）考察v3:

T(v5)=min[T(v5)，P(v3)+a35]＝min[∞，4＋1]=5T(v4)=min[T(v4)，P(v3)+a34]＝min[9，4＋4]=8所以，P(v5)=5（5）考察v5:T(v6)=min[T(v6)，P(v5)+a56]＝min[∞，5＋6]=11T(v4)=min[T(v4)，P(v5)+a54]＝min[8，5＋2]=7所以，P(v4)=7

8T(v6)=11

11（7）P(v4)=7

二、最短路問(wèn)題的算法

（3）（4）v6v5v3v1v4v236511243611(0)（5）（7）（6）考察v4:T(v6)=min[T(v6)，P(v4)+a46]＝min[11，7＋3]=10所以，P(v6)=10所有點(diǎn)都標(biāo)上P標(biāo)號(hào)．

P(v6)=10(10)(7)標(biāo)出最短路v1到v6的最短路可從v1開(kāi)始，根據(jù)永久性標(biāo)號(hào)數(shù)值回溯得到．(7)標(biāo)出最短路最短路徑是：v1→v2→v3→v5→v4→v6，路長(zhǎng)10．同時(shí)得到，到其余各點(diǎn)的最短路，即各點(diǎn)的永久性標(biāo)號(hào)P（vi）．

注意：雙標(biāo)號(hào)法只適用于所有wij

≥0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時(shí)，則算法失效．

（3）（4）v6v5v3v1v4v2365112436(0)（5）（7）(10)二、最短路問(wèn)題的算法

例6.1設(shè)有一批貨物要從v1運(yùn)到v7，求最短運(yùn)輸路線。解：v1v2v3v5v6v7142157326

v4420,V2(1)v1v2v3v5v6v7142157326

v44201,V3(3)v1v2v3v5v6v7142157326

v442013,V6(4)v1v2v3v5v6v7142157326

v4420134,V4(5)v1v2v3v5v6v7142157326

v44201345,V5(7)v1v2v3v5v6v7142157326

v442013457,V7(9)v1v2v3v5v6v7142157326

v4420134579得最短路：V1V2V4V5V7：V1V2V3V6V5V7

例6.2設(shè)有一批貨物要從v1運(yùn)到v7，求最短運(yùn)輸路線。解：v1v2v3v5v6v7142157326v442二、最短路的矩陣算法解：先將圖表示為矩陣形式。v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2102475V34201V4402V572032V651306V7260第一步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2102475V34201V4402V572032V651306V7260112+14+17+15+13586第二步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34201V4402V572032V651306V7260111+3433第三步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4402V572032V651306V7260113+4733446+410第四步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4402V572032V6517010V7260112+57334455第五步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4407V572032V6517010V7260112+79334455777第六步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4407V572039V6517010V7260112+7933445577799v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4407V572039V6