（第十五講）

紹興文理學院計算機系計算機應用教研室數據結構（第十五講）紹興文理學院計算機系計算機應用教研室數連通網絡的最小代價

問題連通網絡的最小代價

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

minimumcostspanningtree

)1、最小生成樹的概念

▲

通信網問題。圖的頂點之間的邊上的權值表示相應的代價，對于n個頂點的連通圖可以建立許多不同的生成樹。

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

▲各邊代價之和最小的那棵生成樹稱為該連通網的最小代價生成樹，簡稱為最小生成樹。2、求解最小生成樹的基礎

▲MST性質：uvUV—UTKS400:58

設G=(V，E)是一個連通網絡，

▲

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

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

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

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

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

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

v5

v1

v2

v3

v4

v6

v1v2v3v4v5v6105666107121015

v5

v1

v2

v3

v4

v6

示例2：TKS600:58

(2)算法步驟(構造過程)假設N=(V，E)是連通(3)普里姆算法的實現

①鄰接矩陣結構typedefstruct{charvexs[mvnum];intarcs[mvnum][mvnum];intvexnum,arcnum;}amgraph;②記錄前驅頂點和V(T)中到V-V(T)權值最小的邊的存儲空間struct{intadjvex；intlowcost；}closedge[nvnum]；③算法實現

Ⅰ初始化：首先將初始頂點甜加入U中，對其余的每一個頂點vi，將closedge[i]均初始化為到u的邊信息。

Ⅱ

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

b、將k加入U中；

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

(3)普里姆算法的實現①鄰接矩陣結構②記錄前驅頂點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

生成樹可能不唯一TKS800:58

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;TKS900:58

⑤算法描述voidminispantree_prim(for(i=1;i<g.vexnum;i++)//重復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;//把頂點vexs[k]加入到Tfor(j=0;j<g.vexnum;j++)//調整 if(g.arcs[k][j]<closedge[j].lowcost)

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

}getch();

}}算法6.8普里姆算法S15_1TKS1000:58

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

時間復雜度：4、克魯斯卡爾算法(1)克魯斯卡爾算法的構造過程設連通網絡N={V,E},將N中的邊按權值從小到大的順序排列。

①最初先構造一個只有n個頂點，沒有邊的非連通圖T={V,},圖中每個頂點自成一個連通分量。

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

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

③重復②，直至T

中所有頂點都在同一個連通分量上為止。TKS1100:58

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

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

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

①輔助數據結構Ⅰ存儲邊信息的結構體(數組edge)

structedgenode{inthead;//邊的始點inttail;//邊的終點intlowcost;//邊上的權值};

Ⅱ標識各頂點連通分量數組

vexset[arcnum]

對每個頂點vi∈V，對應元素vexset[i]表示該頂點所在的連通分量。初始時：vexset[i]=i，表示各頂點自成一個連通分量。

TKS1300:58

(3)克魯斯卡爾算法的實現①輔助數據結構TKS1321②算法思想Ⅰ將邊信息數組edge中的元素按權值從小到大排序。

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

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

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

②算法思想Ⅰ將邊信息數組edge中的元素按權值從小到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_2TKS1500:58

sort(g);for(i=0;i<g.vexnum④算法分析

時間復雜度：○(n×e)～○(e×loge)(4)

比較兩種算法比較算法名普里姆算法克魯斯卡爾算法時間復雜度

○(n2)○(n×e)

適應范圍稠密圖稀疏圖

？五、作業(yè)：

1、書面作業(yè)：P161：2中(1)、(2)、(3)

2、實踐：實驗二、棧序列匹配TKS1600:58

④算法分析時間復雜度：○(n×e)～○(e×loge（第十五講）

紹興文理學院計算機系計算機應用教研室數據結構（第十五講）紹興文理學院計算機系計算機應用教研室數連通網絡的最小代價

問題連通網絡的最小代價

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

minimumcostspanningtree

)1、最小生成樹的概念

▲

通信網問題。圖的頂點之間的邊上的權值表示相應的代價，對于n個頂點的連通圖可以建立許多不同的生成樹。

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

▲各邊代價之和最小的那棵生成樹稱為該連通網的最小代價生成樹，簡稱為最小生成樹。2、求解最小生成樹的基礎

▲MST性質：uvUV—UTKS2000:58

設G=(V，E)是一個連通網絡，

▲

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

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

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

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

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

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

v5

v1

v2

v3

v4

v6

v1v2v3v4v5v6105666107121015

v5

v1

v2

v3

v4

v6

示例2：TKS2200:58

(2)算法步驟(構造過程)假設N=(V，E)是連通(3)普里姆算法的實現

①鄰接矩陣結構typedefstruct{charvexs[mvnum];intarcs[mvnum][mvnum];intvexnum,arcnum;}amgraph;②記錄前驅頂點和V(T)中到V-V(T)權值最小的邊的存儲空間struct{intadjvex；intlowcost；}closedge[nvnum]；③算法實現

Ⅰ初始化：首先將初始頂點甜加入U中，對其余的每一個頂點vi，將closedge[i]均初始化為到u的邊信息。

Ⅱ

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

b、將k加入U中；

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

(3)普里姆算法的實現①鄰接矩陣結構②記錄前驅頂點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

生成樹可能不唯一TKS2400:58

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;TKS2500:58

⑤算法描述voidminispantree_prim(for(i=1;i<g.vexnum;i++)//重復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;//把頂點vexs[k]加入到Tfor(j=0;j<g.vexnum;j++)//調整 if(g.arcs[k][j]<closedge[j].lowcost)

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

}getch();

}}算法6.8普里姆算法S15_1TKS2600:58

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

時間復雜度：4、克魯斯卡爾算法(1)克魯斯卡爾算法的構造過程設連通網絡N={V,E},將N中的邊按權值從小到大的順序排列。

①最初先構造一個只有n個頂點，沒有邊的非連通圖T={V,},圖中每個頂點自成一個連通分量。

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

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

③重復②，直至T

中所有頂點都在同一個連通分量上為止。TKS2700:58

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

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

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

①輔助數據結構Ⅰ存儲邊信息的結構體(數組edge)

structedgenode{inthead;//邊的始點inttail;//邊的終點intlowcost;//邊上的權值};

Ⅱ標識各頂點連通分量數組

vexset[arcnum]

對每個頂點vi∈V，對應元素vexset[i]表示該頂點所在的連通分量。初始時：vexset[i]=i，表示各頂點自成一個連通分量。

TKS2900:58

(3)克魯斯卡爾算法