数据结构课件第三讲

第三讲生成树生成树定义：所有顶点均由边连接在一起，但不存在回路的图叫～深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的～说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树GHKIV1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林最小生成树问题提出要在n个城市间建立通信联络网，顶点——表示城市权——城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小———最小代价生成树问题分析1654327131791812752410n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小构造最小生成树方法方法一：普里姆(Prim)算法算法思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树Ch6_3.cV3V1V4V6V5V23652165546如何求连通图的最小生成树?？

求解:

连通6个城市且代价最小的交通线路?V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U={V1}U={V1,V3}U={V1,V3,V6}U={V1,V3,V6,V4}U={V1,V3,V6,V4,V2}U={V1,V3,V6,V4,V2,V5}

有关数据的存储结构

无向连通网络:

G

为选择权值最小的边:

置一个一维数组：closedge[]，以记录从U到

V-U具有最小代价的边。对每一顶点vi

V-U,在辅助数组中相应分量closedge[i-1],包括两域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存储该边上的权Closedge[i-1].adjvex域：存储该边依附的在U中的顶点。

普鲁姆算法涉及的数据和操作：

数据：无向连通网络

操作:

选择权值最小的边，不妨设为（u,v)

(u,v)加入TE，u加入UUV-U

viV2V0V3V5V4V-U

vivjV3V1V4V6V5V23652165546例000000

06

1

5maxmax

viadjvexlowcost

012345

viadjvexlowcost

012345020022

05056

4U={v1}U={v1,v3}V3V1V4V6V5V23652165546UU对每一顶点vi

V-U,在辅助数组中相应分量closedge[i-1],包括两域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存储该边上的权Closedge[i-1].adjvex域：存储该边依附的在U中的顶点。V-U={v2,V3,V4,V5,V6}V-U={v2,V4,V5,V6}

0v1v1v100

06

1

5maxmax

lowcost{v1}

0v30v1v3v3

05056

4

adjvexlowcost{v1,v3}

0v30v6v32

050

2

60

adjvexlowcost{v1,v3,v6}

0v305v32

0

5

0060

adjvexlowcost{v1,v3,v6,v4}

0205v22

0000

3

0adjvexlowcost{v1,v3,v6,v4,v2}

020512

000000

adjvexlowcost{v1,v3,v6,v4,v2,v5}iadjvex

012345UV3V1V4V6V5V23652165546closedgev1v2v3v4v5v6用普里姆算法viudPRIM(MGraphG,VertexTypeu){k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)if(j!=k)closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=mininmum(closedge);printf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum.++j)if(G.arcs[k][j].adj<closedge[j].lowcostclosedge[j]={G.vexs[k],G.arcs[k][j].adj}}}方法二：克鲁斯卡尔(Kruskal)算法算法思想：设连通网N=(V,{E})，令最小生成树初始状态为只