第十五讲图3-数据结构课件

（第十五讲）

绍兴文理学院计算机系计算机应用教研室数据结构（第十五讲）绍兴文理学院计算机系计算机应用教研室数连通网络的最小代价

问题连通网络的最小代价

问题第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—UTKS415:57

设G=(V，E)是一个连通网络，

▲

普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST性质构造最小生成树的算法。3、普里姆算法(1)算法思想从连通网络N={V,E}中的某一顶点V(T)={u0}出发，选择与它关联的具有最小权值的边(u0,v)，将其以后每一步从一个顶点在V(T)中，而另一个顶点不在V(T)中的各条边中选择权值最小的边(u，v),把它的顶点v加入到集合V(T)中，将其边(u,v)加入到生成树的边集合E(T)中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合V(T)中为止(直到V(T)满n个顶点为止)。顶点v加入到生成树的顶点集合V(T)中，V(T)TKS515:57

▲普里姆(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：TKS615:57

(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的边信息。

Ⅱ

循环n-l次，做加下处理：a、从各组最小边closedge[v]中选出最小的最小边closedge[k]，输出此边(v，k∈V-U)；

b、将k加入U中；

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

(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

生成树可能不唯一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++)//重复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_1TKS1015:57

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

时间复杂度：4、克鲁斯卡尔算法(1)克鲁斯卡尔算法的构造过程设连通网络N={V,E},将N中的边按权值从小到大的顺序排列。

①最初先构造一个只有n个顶点，没有边的非连通图T={V,

},图中每个顶点自成一个连通分量。

②在E中选择权值最小的边，若该边依附的两个顶点落在T中不同的连通分量上(即不形成回路)，则将此边加入到T

中；否则将此边舍去，重新选择下一条权值最小的边。

③重复②，直至T

中所有顶点都在同一个连通分量上为止。TKS1115:57

⑥算法分析时间复杂度：4、克鲁斯卡尔算法TKS111即(算法步骤)令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生成树可能不唯一TKS1215:57

即(算法步骤)令V(T)=V(G);E(T)=；v(3)克鲁斯卡尔算法的实现

①辅助数据结构Ⅰ存储边信息的结构体(数组edge)

structedgenode{inthead;//边的始点inttail;//边的终点intlowcost;//边上的权值};

Ⅱ标识各顶点连通分量数组

vexset[arcnum]

对每个顶点vi∈V，对应元素vexset[i]表示该顶点所在的连通分量。初始时：vexset[i]=i，表示各顶点自成一个连通分量。

TKS1315:57

(3)克鲁斯卡尔算法的实现①辅助数据结构TKS1310②算法思想Ⅰ将边信息数组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];TKS1415:57

②算法思想Ⅰ将边信息数组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_2TKS1515:57

so