7.4图的连通性问题(连通网的)最小生成树回顾：生成树？一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，
且只含有足以构成一棵树的n-1条边。V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V
4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V661
55664235V1V2V3V4V5V666625V1V2V3V4V5V61
4235V1V2V3V4V5V615623权值之和为25权值之和为15权值之和为18
假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？
最小生成树应用问题：等价于构造网的一棵最小生成树。即:在e条带权的边中选取n-1条边（不构成回路），使“权
值之和”最小。算法二：（克鲁斯卡尔算法）算法一：（普里姆算法）（重点）求最小生成树算法取图中任意一个顶点v作为生
成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通
顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n个顶点为止。普里姆算法的基本思想:V1
V2V3V4V5V66155664235V1V31V6V4425V2V53权
值之和为15假设连通图N=（V，{E}）TE是N上最小生成树中边的集合算法的初始状态：U={u0}
u0∈VTE={}算法的重复执行以下操作：（1）在从U中所有的顶点到V-U中的所有顶点中的边
中找一条权值最小的边（u0,v0)，并入集合TE中。（2）将v0并入U中，直到U=V为止。此时TE中必
有n-1条边，则T=（V，{TE}）为N的最小生成树。abcdegf例如:195141827168
213127所得生成树权值和=14+8+3+5+16+21=67aedcbgf14853
1621练习:V165V2V4V3V5V655264631V2V4V3V5V6V1
黄色顶点为集合U绿色顶点为集合V-U1V33524V6V4V2V5在生成树的构造过程
中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中
顶点的边中选取权值最小的边。一般情况下所添加的顶点应满足下列条件:UV-U采用普里姆算法求最小生成树时关键问
题？如何从U中顶点u0到V-U中顶点v0的所有边中找权值最小的边？无向连通网采用数组表示法存储
为了解决上述关键问题，普里姆算法引进一个辅助数组closedge,以记录从U到V-U具有最小代价的边。其中每个分量close
dge[i]记录了从U中所有顶点到V-U中的一个顶点代价最小的边。struct{VertexTypeadjv
ex;//U集中的顶点VRTypelowcost;//边的权值}closedge[
MAX_VERTEX_NUM];对每个顶点vi∈V-U在closedge数组中存在一个相应的分量closedge[
i-1]。closedge[i-1].lowcost=Min{cost(u,vi)}初始态
i12345U
V-UKclosedgeadjvexlo
wcostv16v11v15v2v3v4v5v6v1k=LocateVex(G,u);
for(i=1;idj};k=mininum(closedge)printf(closedge[k].adjvex,G.vexs[
k];closedge[k].lowcost=0;2adjvexlow
costv16v15v10v2v4v5v6v1v3if(G.arcs[k][j].adje[j].lowcost)closedge[j]={G.vexs[k],G.arcs{k][j].adj};
adjvexlowcostv10v35v15v36v34v1
v3v2v4v5v6for(j=0;jprintf(closedge[k].adjvex,G.vexs[k];closedge[k].lowcost=0;
adjvexlowcost5v35v10v15v36v30
v2v4v5v1v3v6adjvexlowcostv35v10
v62v36v30v1v3v6v2v4v53adjvexl
owcostv35v10v36v30v60v1v3v6v4v2v5adjvex
lowcostv35v10v36v30v60v1v3v6v4v2v5v3
0v5v1v3v6v4v21v234v20V1v3v6v4v2v5voidMiniSpanTree_P
(MGraphG,VertexTypeu){k
=LocateVex(G,u);for(j=0;j//辅助数组初始化if(j!=k)clos
edge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;
for(i=1;i//求出加入生成树的下一个顶点(k)printf(closedge[k].
adjvex,G.vexs[k]);//输出生成树上一条边
closedge[k].lowcost=0;//第k顶点并入for(j=0;j;++j)//修改其它顶点的最小边if(G.arcs[k][
j].adjG.arcs[k][j].adj};}}
具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG
上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边
的权值尽可能地小。克鲁斯卡尔算法的基本思想：例如:V165V2V4V3V5V655264631
13524V2V4V3V5V6V1普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠
密图稀疏图算法名适应范围比较两种算法V2V4V3V5V6V1V7V8练习:黄色顶点为集合U绿色顶点为
集合V-U7V33243V6V4V2V5V197V2V4V3V5V626464238V73V82122V82V7作业：对下图所示的无向网采用prim算法从顶点A开始构造最小生成树。画出最小生成树，并写出在构造过程中辅助数组中各分量值的变化。ACDB56789预习：7.5节中拓扑排序和关键路径 |
|
