（第十五講）

紹興文理學(xué)院計(jì)算機(jī)系計(jì)算機(jī)應(yīng)用教研室數(shù)據(jù)結(jié)構(gòu)（第十五講）紹興文理學(xué)院計(jì)算機(jī)系計(jì)算機(jī)應(yīng)用教研室數(shù)連通網(wǎng)絡(luò)的最小代價(jià)

問題連通網(wǎng)絡(luò)的最小代價(jià)

問題第6章圖(3)一、教學(xué)目的：明確最小生成樹的概念，掌握求最小生成樹的prim和kruskal方法及prim求解算法；算法設(shè)計(jì)訓(xùn)練。二、教學(xué)重點(diǎn)：最小生成樹的概念，求最小生成樹的prim和kruskal方法及prim求解算法；算法設(shè)計(jì)訓(xùn)練。三、教學(xué)難點(diǎn)：求最小生成樹的prim算法；算法設(shè)計(jì)訓(xùn)練。四、教學(xué)過程：第6章圖(3)一、教學(xué)目的：明確最小生成樹的概念，掌握求設(shè)G=(V，E)是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)非空子集。若(u，v)是一條具有最小權(quán)值(代價(jià))的邊，其中u∈U，v∈V-U，則必存在一棵包含邊(u，v)的最小生成樹。(證明略)§6.4圖的應(yīng)用§6.4.1最小生成樹(

minimumcostspanningtree

)1、最小生成樹的概念

▲

通信網(wǎng)問題。圖的頂點(diǎn)之間的邊上的權(quán)值表示相應(yīng)的代價(jià)，對(duì)于n個(gè)頂點(diǎn)的連通圖可以建立許多不同的生成樹。

▲一棵生成樹的代價(jià)就是樹上各邊的代價(jià)之和。

▲各邊代價(jià)之和最小的那棵生成樹稱為該連通網(wǎng)的最小代價(jià)生成樹，簡(jiǎn)稱為最小生成樹。2、求解最小生成樹的基礎(chǔ)

▲MST性質(zhì)：uvUV—UTKS415:57

設(shè)G=(V，E)是一個(gè)連通網(wǎng)絡(luò)，

▲

普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法是兩個(gè)利用MST性質(zhì)構(gòu)造最小生成樹的算法。3、普里姆算法(1)算法思想從連通網(wǎng)絡(luò)N={V,E}中的某一頂點(diǎn)V(T)={u0}出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v)，將其以后每一步從一個(gè)頂點(diǎn)在V(T)中，而另一個(gè)頂點(diǎn)不在V(T)中的各條邊中選擇權(quán)值最小的邊(u，v),把它的頂點(diǎn)v加入到集合V(T)中，將其邊(u,v)加入到生成樹的邊集合E(T)中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合V(T)中為止(直到V(T)滿n個(gè)頂點(diǎn)為止)。頂點(diǎn)v加入到生成樹的頂點(diǎn)集合V(T)中，V(T)TKS515:57

▲普里姆(Prim)算法和克魯斯卡爾(Kruskal)(2)

算法步驟(構(gòu)造過程)假設(shè)N=(V，E)是連通網(wǎng)，TE是N上最小生成樹中邊的集合。

①U={u0}(u0∈V)，TE={}。

②在所有u∈U，v∈V-U的邊(u，v)∈E中找一條權(quán)值最小的邊(u0，v0)并入集合TE，同時(shí)v0并入U(xiǎn)。

③重復(fù)②，直至U=V為止。此時(shí)TE中必有n-l條邊，則T=(V，TE)為N的最小生成樹。示例1：v1v2v3v4v5v63552461566

v5

v1

v2

v3

v4

v6

v1v2v3v4v5v6105666107121015

v5

v1

v2

v3

v4

v6

示例2：TKS615:57

(2)算法步驟(構(gòu)造過程)假設(shè)N=(V，E)是連通(3)普里姆算法的實(shí)現(xiàn)

①鄰接矩陣結(jié)構(gòu)typedefstruct{charvexs[mvnum];intarcs[mvnum][mvnum];intvexnum,arcnum;}amgraph;②記錄前驅(qū)頂點(diǎn)和V(T)中到V-V(T)權(quán)值最小的邊的存儲(chǔ)空間struct{intadjvex；intlowcost；}closedge[nvnum]；③算法實(shí)現(xiàn)

Ⅰ初始化：首先將初始頂點(diǎn)甜加入U(xiǎn)中，對(duì)其余的每一個(gè)頂點(diǎn)vi，將closedge[i]均初始化為到u的邊信息。

Ⅱ

循環(huán)n-l次，做加下處理：a、從各組最小邊closedge[v]中選出最小的最小邊closedge[k]，輸出此邊(v，k∈V-U)；

b、將k加入U(xiǎn)中；

c、更新剩余的每組最小邊信息closedge[v]，(v∈V-U)。TKS715:57

(3)普里姆算法的實(shí)現(xiàn)①鄰接矩陣結(jié)構(gòu)②記錄前驅(qū)頂點(diǎn)v1v2v3v4v5v6105666107121015lowcostadjvexlowcostadjvexlowcost

adjvexlowcostadjvexlowcostadjvexlowcostadjvexk

V-T(V)

T(V)

V6V5V4V3V2V

closedge

v5

v1

1{V2V3V4V5V6}

{V1}121510V1V1V1

2{V3V4V5V6}{V1V2}V2V1V2V2

v2

7156503

v3

{V4V5V6}{V1V2V3}715600V2V1V24

v4

{V5V6}{V1V2V3V4}610000V4V46

v6

{V5}{V1V2V3V4V6}010000V45∮

{V1V2V3V4V6V5}00000

④示例v1v2v3v4v5v6105666107121015

生成樹可能不唯一TKS815:57

v1v2v3v4v5v6105666107121015low⑤算法描述voidminispantree_prim(amgraphg,charu)//普里姆算法{struct{intadjvex;intlowcost;}closedge[mvnum];inti,j,k,min;k=locatevex(g,u,g.vexnum);//初始化for(j=0;j<g.vexnum;j++)if(j!=k){closedge[j].adjvex=k;closedge[j].lowcost=g.arcs[k][j];}closedge[k].lowcost=0;TKS915:57

⑤算法描述voidminispantree_prim(for(i=1;i<g.vexnum;i++)//重復(fù)n-1次做

{min=maxint;for(j=0;j<g.vexnum;j++)if(closedge[j].lowcost>0&&closedge[j].lowcost<min)

{min=closedge[j].lowcost;k=j;}printf("%c--%2d-->%c",g.vexs[closedge[k].adjvex],closedge[k].lowcost,g.vexs[k]);//輸出closedge[k].lowcost=0;//把頂點(diǎn)vexs[k]加入到Tfor(j=0;j<g.vexnum;j++)//調(diào)整 if(g.arcs[k][j]<closedge[j].lowcost)

{closedge[j].adjvex=k;closedge[j].lowcost=g.arcs[k][j];

}getch();

}}算法6.8普里姆算法S15_1TKS1015:57

for(i=1;i<g.vexnum;i++)//⑥算法分析

時(shí)間復(fù)雜度：4、克魯斯卡爾算法(1)克魯斯卡爾算法的構(gòu)造過程設(shè)連通網(wǎng)絡(luò)N={V,E},將N中的邊按權(quán)值從小到大的順序排列。

①最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn)，沒有邊的非連通圖T={V,

},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。

②在E中選擇權(quán)值最小的邊，若該邊依附的兩個(gè)頂點(diǎn)落在T中不同的連通分量上(即不形成回路)，則將此邊加入到T

中；否則將此邊舍去，重新選擇下一條權(quán)值最小的邊。

③重復(fù)②，直至T

中所有頂點(diǎn)都在同一個(gè)連通分量上為止。TKS1115:57

⑥算法分析時(shí)間復(fù)雜度：4、克魯斯卡爾算法TKS111即(算法步驟)令V(T)=V(G);E(T)=

；WHILE(E(T)中的邊數(shù)＜n-1){從E(G)中選取權(quán)數(shù)最小的邊(vi,vj);IF((vi,vj)在T中不構(gòu)成圈)加邊(vi,vj)到E(T)中；將邊(vi,vj)從E(G)中刪去;}(2)示例v1v2v3v4v5v6105666107121015v1v2v3v4v5v61056661071210155661010生成樹可能不唯一TKS1215:57

即(算法步驟)令V(T)=V(G);E(T)=；v(3)克魯斯卡爾算法的實(shí)現(xiàn)

①輔助數(shù)據(jù)結(jié)構(gòu)Ⅰ存儲(chǔ)邊信息的結(jié)構(gòu)體(數(shù)組edge)

structedgenode{inthead;//邊的始點(diǎn)inttail;//邊的終點(diǎn)intlowcost;//邊上的權(quán)值};

Ⅱ標(biāo)識(shí)各頂點(diǎn)連通分量數(shù)組

vexset[arcnum]

對(duì)每個(gè)頂點(diǎn)vi∈V，對(duì)應(yīng)元素vexset[i]表示該頂點(diǎn)所在的連通分量。初始時(shí)：vexset[i]=i，表示各頂點(diǎn)自成一個(gè)連通分量。

TKS1315:57

(3)克魯斯卡爾算法的實(shí)現(xiàn)①輔助數(shù)據(jù)結(jié)構(gòu)TKS1310②算法思想Ⅰ將邊信息數(shù)組edge中的元素按權(quán)值從小到大排序。

Ⅱ依次從排好序的數(shù)組edge中選出一條邊(vl，v2)，在vexset中分別查找vl和v2所在的連通分量VS1和VS2。若VS1和VS2不等，表明所選的兩個(gè)頂點(diǎn)分屬不同的連通分量，輸出此邊，并合并VS1和VS2兩個(gè)連通分量；若VS1和VS2相等，表明所選的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，舍去此邊而選擇下一條權(quán)值最小的邊。

Ⅲ重復(fù)Ⅱ(n-1次)，直至edge中所有的邊都掃描判斷完，并且所有頂點(diǎn)都在同一連通分量上。

③算法描述voidminispantree_kruskal(amgraphg){inti,j,v1,v2,vs1,vs2,*vexset;vexset=newint[g.vexnum];TKS1415:57

②算法思想Ⅰ將邊信息數(shù)組edge中的元素按權(quán)值從小到sort(g);for(i=0;i<g.vexnum;i++)vexset[i]=i;for(i=0;i<g.arcnum;i++){v1=g.edge[i].head;v2=g.edge[i].tail;vs1=vexset[v1];vs2=vexset[v2];if(vs1!=vs2){printf("%c--%2d-->%c",g.vexs[v1],g.edge[i].lowcost,g.vexs[v2]); for(j=0;j<g.vexnum;j++)if(vexset[j]==vs2)vexset[j]=vs1;}}}算法6.9克魯斯卡爾算法S15_2TKS1515:57

so