数据结构-从概念到C++实现（第4版）课件 5-4最小生成树

5-4最小生成树v第五章图最小生成树的定义v0v1v2v4v3生成树：连通图的生成树是包含全部顶点的一个极小连通子图含有n-1条边多——构成回路少——不连通v0v1v2v4v3v0v1v2v4v3v3v2v1v4v0v0v1v2v4v3可以指定根结点生成树可能不唯一生成树的代价：在无向连通网中，生成树上各边的权值之和最小生成树：在无向连通网中，代价最小的生成树v0v1v2v4v32785636v0v1v2v4v3275生成树的代价：20v0v1v2v4v32563生成树的代价：16最小生成树的定义在n个城市之间建造通信网络，至少要架设n-1条通信线路，每两个城市之间架设通信线路的造价是不一样的，如何设计才能使得总造价最小？Prim算法Kruskal算法学什么？5-4-1Prim算法v第五章图基本思想算法：Prim输入：无向连通网G=(V，E)输出：最小生成树T=(U，TE)1.初始化：U={v}；TE={}；2.重复下述操作直到U=V：2.1在E中寻找最短边(i，j)，且满足i∈U，j∈V-U；2.2U=U+{j}；2.3TE=TE+{(i，j)}；关键：如何找到连接U和V-U的最短边？uvv'顶点集U顶点集V-Uminv0v1v2v4v3v5341219262525463817关键：是如何找到连接U和V-U的最短边？

U：涂色

V-U：尚未涂色方法：一个顶点涂色、另一个顶点尚未涂色的最短边v0v1v2v4v3v51219262517基本思想v0运行实例初始化：U={v0}V-U={v1,v2,v3,v4,v5}cost={(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}v0v519第一次迭代：U={v0

,v5}V-U={v1,v2,v3,v4}cost={(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26}v0v1v2v4v3v5341219262525463817v0v519v225第二次迭代：U={v0

,v5,v2}V-U={v1,v3,v4}cost={(v0,v1)34,(v2,v3)17,(v5,v4)26}v0v2v51925v317第三次迭代：U={v0

,v5,

v2,v3}V-U={v1,v4}cost={(v0,v1)34,(v5,v4)26}第一次迭代：cost={(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26}运行实例v0v1v2v4v3v5341219262525463817v426v0v2v3v5192517第四次迭代：U={v0

,v5,

v2,v3,v4}V-U={v1}cost={(v4,v1)12}v112v0v2v4v3v519262517第三次迭代：cost={(v0,v1)34,(v5,v4)26运行实例v0v1v2v4v3v5341219262525463817存储结构需要不断读取任意两个顶点之间边的权值图采用什么存储结构？图采用邻接矩阵存储如何存储候选最短边集（连接U和V-U的候选最短边）？数组adjvex[n]：表示候选最短边的邻接点数组lowcost[n]：表示候选最短边的权值adjvex[i]=jlowcost[i]=w例如：{(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}含义是：候选最短边（i,j）的权值为w，其中i∈V-U，j∈U初始时，lowcost[v]=0，表示将顶点v加入集合U中；

adjvex[i]=v，lowcost[i]=edge[v][i]（0≤i

≤n-1）例如：{(v0,v0)0,(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}000000adjvex[n]=012345

03446∞

∞19lowcost[n]=存储结构每一次迭代，设数组lowcost[n]中的最小权值是lowcost[j]，则

令lowcost[j]=0，表示将顶点j加入集合U中；例如：{(v0,v0)0,(v0,v1)34,(v0,v2)46,(v0,v3)∞,(v0,v4)∞,(v0,v5)19}更新：{(v0,v0)0,(v0,v1)34,(v5,v2)25,(v5,v3)25,(v5,v4)26,(v0,v5)0}lowcost[i]=min{lowcost[i],edge[i][j]}adjvex[i]=j（如果edge[i][j]<lowcost[i]）（0≤i≤n-1）由于顶点j从集合V-U进入集合U，候选最短边集发生变化，需要更新：012345

000000adjvex[n]=

03446∞

∞19lowcost[n]=

005

550adjvex[n]=

034252526

0lowcost[n]=012345存储结构v0v1v2v4v3v5341219262525463817v0000340460∞0∞019

Vv0

v1

v2

v3

v4

v5U输出

adjvexlowcost下标012345voidPrim(intv)/*假设从顶点v出发*/{inti,j,k,adjvex[MaxSize],lowcost[MaxSize];

lowcost[v]=0;/*将顶点v加入集合U*/for(i=0;i<vertexNum;i++)/*初始化辅助数组shortEdge*/{lowcost[i]=edge[v][i];adjvex[i]=v;}算法实现v0000340460∞0∞019(v0,v5)19

Vv0

v1

v2

v3

v4

v5U输出

adjvexlowcostadjvexlowcost下标012345v0,v503452552552600v0v1v2v4v3v5341219262525463817for(k=1;k<vertexNum;i++)/*迭代n-1次*/{j=MinEdge(lowcost,vertexNum)/*寻找最短边的邻接点j*/cout<<j<<adjvex[j]<<lowcost[j];lowcost[j]=0;

}for(i=0;i<vertexNum;i++)/*调整数组shortEdge[n]*/if(edge[i][j]<lowcost[i]){lowcost[i]=edge[i][j];adjvex[i]=j;}算法实现v0v1v2v4v3v5341219262525463817v0,v5,v2,v3,v4,v1(v4,v1)12v0000340460∞0∞019(v0,v5)19

Vv0

v1

v2

v3

v4

v5U输出

adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcost下标012345v0,v503452552552600(v5,v2)25v0,v5,v203450217526(v2,v3)17v0,v5,v2,v303420526(v5,v4)26v0,v5,v2,v3,v44125040v0v1v2v4v3v51219262517验证算法voidPrim(intv){inti,j,k,adjvex[MaxSize],lowcost[MaxSize];}O(n)O(n)O(n)时间复杂度？O(n2)for(i=0;i<vertexNum;i++)if(edge[i][j]<lowcost[i]){lowcost[i]=edge[i][j];adjvex[i]=j;}for(i=0;i<vertexNum;i++){lowcost[i]=edge[v][i];adjvex[i]=v;}lowcost[v]=0;for(k=1;k<vertexNum;i++){j=MinEdge(lowcost,vertexNum)cout<<j<<adjvex[j]<<lowcost[j];lowcost[j]=0;

}算法实现5-4-2Kruskal算法v第五章图基本思想找到连接U和V-U的最短边Prim算法的关键是什么？最短边顶点分别位于U和V-U中Prim算法：先构造满足条件的候选最短边集，再查找最短边Kruskal算法：先查找最短边，再判断是否满足条件算法：Kruskal算法输入：无向连通网G=(V,E)输出：最小生成树T=(U,TE)1.初始化：U=V；TE={}；

2.重复下述操作直到所有顶点位于一个连通分量：2.1在E中选取最短边(u,v);2.2如果顶点

u、v

位于两个连通分量，则2.2.1TE=TE+{(u,v)}；2.2.2将这两个连通分量合成一个连通分量；2.3在

E

中标记边(u,v)，使得(u,v)不参加后续最短边的选取；基本思想关键：如何判断、合并顶点位于的连通分量？v0v1v2v4v3v5341219262525463817初始化：连通分量＝{v0},{v1},{v2},{v3},{v4},{v5}第一次迭代：连通分量＝{v0},{v1,v4},{v2},{v3},{v5}第二次迭代：连通分量＝{v0},{v1,v4},{v2,v3},{v5}第三次迭代：连通分量＝{v0,v5},{v1,v4},{v2,v3}第四次迭代：连通分量＝{v0,v2,v3,v5},{v1,v4}v0v1v2v4v3v51217252619第五次迭代：连通分量＝{v0,v2,v3,v5,v1,v4}运行实例图采用什么存储结构呢？边集数组表示法存储结构算法：Kruskal算法输入：无向连通网G=(V,E)输出：最小生成树T=(U,TE)1.初始化：U=V；TE={}；

2.重复下述操作直到所有顶点位于一个连通分量：2.1在

E中选取最短边(u,v);2.2如果顶点

u、v

位于两个连通分量，则2.2.1TE=TE+{(u,v)}；2.2.2将这两个连通分量合成一个连通分量；2.3在

E

中标记边(u,v)，使得(u,v)不参加后续最短边的选取；v0v1v2v4v3v5341219262525463817v0

v1

v2

v3

v4

v5下标：012345

0519

2317

2525

3525

4526

0134

3438

0246

1412fromtoweight图采用什么存储结构呢？边集数组表示法存储结构v0

v1

v2

v3

v4

v5下标：012345

0519

2317

2525

3525

4526

3438

0134

0246

1412fromtoweightconstintMaxVertex=10;constintMaxEdge=100;template<typenameDataType>classEdgeGraph{public:

EdgeGraph(DataTypea[],intn,inte);

~EdgeGraph();

voidKruskal();private:

intFindRoot(intparent[],intv)

DataTypevertex[MaxVertex];

EdgeTypeedge[MaxEdge];

intvertexNum,edgeNum;};如何定义边集数组表示法？存储结构如何存储连通分量呢？并查集{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5{v0,v5,v2,v3},{v1,v4}v2v1v3v4v5v0并查集：集合中的元素组织成树的形式：（1）查找两个元素是否属于同一集合：所在树的根结点是否相同（2）合并两个集合——将一个集合的根结点作为另一个集合根结点的孩子存储结构如何存储并查集呢？双亲表示法{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5v0

v1

v2

v3

v4

v5下标：012345vertexparent[n]-1-1-1210parent存储结构并查集：集合中的元素组织成树的形式：（1）查找两个元素是否属于同一集合：所在树的根结点是否相同（2）合并两个集合——将一个集合的根结点作为另一个集合根结点的孩子v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5121719{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5-1-1-1210下标：012345parent如何判断两个顶点是否位于同一个连通分量呢？intFindRoot(intparent[],intv){intt=v;while(parent[t]>-1)t=parent[t];returnt;}vex1=FindRoot(parent,i);vex2=FindRoot(parent,j);if(vex1!=vex2){}例如，边(v2,v5)运行实例{v0,v5},{v1,v4},{v2,v3}v0v1v2v4v3v5-1-1-1210下标：012345parent如何合并两个连通分量呢？vex1=FindRoot(parent,i);vex2=FindRoot(parent,j);if(vex1!=vex2){

}parent[vex2]=vex1;{v0,v5,v2,v3},{v1,v4}v2v1v3v4v5v02v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5121719运行实例v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5初始化{v0}{v1}{v2}{v3}{v4}{v5}-1-1-1-1-1-1parent

Vv0

v1

v2

v3

v4

v5

最短边

说明

parent下标012345voidKruskal(

){inti,num=0,vex1,vex2;for(i=0;i<vertexNum;i++)parent[i]=-1;}算法实现v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5初始化{v0}{v1}{v2}{v3}{v4}{v5}-1-1-1-1-1-112(v4,v1)12vex1=1,vex2=4,parent[4]=1{v0}{v1,v4}{v2}{v3}{v5}-1-1-1-1

1-117(v2,v3)17vex1=2,vex2=3,parent[3]=2{v0}{v1,v4}{v2,v3}{v5}-1-1-1

2

1-1parent

Vv0

v1

v2

v3

v4

v5

最短边

说明

parent下标012345parentparentfor(num=0,i=0;num<ertexNum;i++){vex1=FindRoot(parent,edge[i].from);vex2=FindRoot(parent,edge[i].to);if(vex1!=vex2){cout<<edge[i].from<<edge[i].to<<edge[i].weight;

parent[vex2]=vex1;

num++;}}算法实现v0v1v2v4v3v5341219262525463817v0v1v2v4v3v5初始化{v0}{v1}{v2}{v3}{v4}{v5}-1-1-1-1-1-112(v4,v1)12vex1=1,vex2=4,parent[4]=1{v0}{v1,v4}{v2}{v3}{v5}-1-1-1-1