《第7章 图结构》习题解答(7)

第7章 图结构

上的权值。

lowcost域的具体含义为：

vi?U??1?closedge[i?1].lowcost??0vi与U不关联

??0v到U的最小权值?i图7.23给出利用普里姆算法在图7.22所示的最小生成树的构造过程中，辅助数组closedge[]

中各个分量值的具体变化情况。图中第一行内的虚线框表示选中顶点4到U中，边(1,4)的权值为1；图中第二行中closedge为选入顶点1、4以后U到V-U的最短距离，其虚线框表示选中顶点2到U中，边(1,2)的权值为2；第三行中closedge为选入顶点1、2、4以后U到V-U的最短距离，其虚线框表示选中顶点3到U中，边(4,3)的权值为2；以此类推，直到全部顶点均被选入为止。

(2)普利姆算法程序实现

定义辅助数组类型CloseDge

struct CloseDge{VType adjvex; int lowcost;};

(1) 函数void MiniTree_Prim(MGraph G,VType u)的功能是，对于邻接矩阵存储的网G，从顶点u开始，用普里姆算法构造一棵最小代价生成树，并输出该树的结点和边的权值。

void MiniTree_Prim(MGraph G,VType u) { int i,j,k,min,max; CloseDge *closedge=new CloseDge[G.vexnum]; if(!(k=LocateVex_MG(G,u)))return; k--; //将k转换为顶点u的下标

-.197.-

第7章 图结构

for(max=G.arcs[0],i=0;i0 && closedge[j].lowcost

(2) 主函数首先建立一个无向网的邻接矩阵G，并显示输出该矩阵，接着从4号顶点开始构造一棵最小生成树并显示输出该树的顶点和所对应的边的权值。

void main() { MGraph G; GKind gk=UDN; cout<<\建立一个无向网的邻接矩阵G:\\n\ CreateGraph_MG(G,gk); cout<<\无向网G的邻接矩阵为:\\n\ DisplyMG(G); cout<<\无向网G的最小生成树为:\\n\ VType u=G.vexs[3].vex;

-.198.-

第7章 图结构

MiniTree_Prim(G,u); }

程序演示结果为：

建立一个无向网的邻接矩阵G:

输入顶点数vexnum和弧数arcnum:5 6↙ 按某种顺序输入5个顶点的值: 1 2 3 4 5↙

输入图中6条边(弧)和权的信息u v w:

1 2 10 1 4 12 2 3 5 2 5 18 3 4 1 3 5 8↙ 无向网G的邻接矩阵为:

0 10 0 12 0 10 0 5 0 18 0 5 0 1 8 12 0 1 0 0 0 18 8 0 0

无向网G的最小生成树为: [4][4,1,3][3,5,2][3,8,5][2,10,1]

说明：

（1）在输出结果的最后一行中，第一项[4]为起始顶点的值，以后每一项为[顶点1,权值,顶点2]。程序运行结果为图7.24所示的无向网(a)，从顶点4开始，由普里姆(prim)算法得到的最小代价生成树(b)。

（2）普里姆(prim)算法的时间复杂度与顶点数n有关而与边的个数无关，其时间复杂度为O(n2)。所以，该算法适用于边数较多的情况。 3．克鲁斯卡尔(Kruskal)算法 (1)克鲁斯卡尔算法思想

克鲁斯卡尔算法的策略是：按照边的权值不减的顺序，依次考察每条边。如果该边和已选的边不构成回路，则选择该边，否则去掉该边。重复执行以上过程直到构造出生成树为止。

设N=(V,VR)是一个连通网，令最小生成树T的初始状态为只有n个顶点而无边的非连通图T=(V,{})，T中每个顶点自成一个连通分量。那么，构造最小生成树的过程为：在VR中选择权值最小的边，若该边依附的两个顶点分别落在T中的两个不同的连通分量上，则将该边加入到T中；否则舍去此边寻找下一条最小代价边。依此类推，直到T为一个连通网为止，此时的T即为最小生成树。

例如，对于图7.21(a)所示的无向网，按照克鲁斯卡尔算法求最小生成树的过程，可以由图7.25(a)到图7.25(f)表示。

-.199.-

第7章 图结构

(2)克鲁斯卡尔算法的程序实现

该算法用到辅助数组edge[]，其中按权值递增的顺序存放网中所有边的信息。数组元素的类型Edge定义为：struct Edge{ VType adjvex; int v1,v2;}; 其中，adjvex为边(v1,v2)的权值。

(1) 函数void EdgeSort(Edge* &edge,MGraph G)的功能是，将以邻接矩阵存储的无向网G中的所有边的信息按权值递增的顺序存储到数组edge[]中

void EdgeSort(Edge* &edge,MGraph G) { int i,j,k,m,w,num=G.arcnum; edge=new Edge[num]; //为edge[]动态分配存储空间 Edge arc; k=0; //k表示edge[]中元素个数，开始时edge[]中有0个元素 for(i=0;i=0;m--) { if(edge[m].adjvex>w) edge[m+1]=edge[m]; else break; } edge[m+1]=arc; k++; } }

(2) 函数void Findedge(ALGraph &G,int u,int v,int& flag)的功能是，用深度优先搜索法在以邻接表存储的无向网G中考察顶点u、v是否在同一个连通分量中，如果在同一个连通分量中则flag=1，否则flag=0。

void Findedge(ALGraph &G,int u,int v,int& flag) { int w; ArcNode* p; G.vertices[u].flag=1; for(p=G.vertices[u].nextarc;p;p=p->nextarc)

-.200.-

第7章 图结构

{ w=p->adjvex; if(w==v){flag=1;return;} if(!G.vertices[w].flag) Findedge(G,w,v,flag); } }

(3) 函数void MiniTree_Kruskal(ALGraph &T,MGraph G)的功能是，用克鲁斯卡尔算法求以邻接矩阵存储的无向网G的最小生成树T，T以邻接表存储。

void MiniTree_Kruskal(ALGraph &T,MGraph G) { int i,k,j,u,v,flag; ArcNode* pr,*pr1; Edge *edge,arc;

/*以下语句的功能是对生成树T进行初始化*/

T.vertices=new VexNode[G.vexnum]; //为T的头结点数组动态分配内存 T.arcnum=G.vexnum-1; //设置T中的边数为n-1条 T.kind=G.kind;

T.vexnum=G.vexnum;

for(i=0;i

EdgeSort(edge,G); //将G的所有边按序存储到edge中 i=k=0; //k表示T中现有边的个数

/*以下语句为Kruskal算法的实现过程*/

while(k

{ arc=edge[i++]; //取一条权值最小的边到arc中 u=arc.v1; v=arc.v2; flag=0; Findedge(T,u,v,flag); //判断u、v是否在同一个连通分量中 if(!flag) //如果arc不在T的同一个连通分量中则将其加入到T中 { pr=new ArcNode; //动态分配单链表结点pr pr->adjvex=v; pr->weight=arc.adjvex; pr->nextarc=T.vertices[u].nextarc; T.vertices[u].nextarc=pr; pr1=new ArcNode; //动态分配单链表结点pr1 pr1->adjvex=u; pr1->weight=arc.adjvex; pr1->nextarc=T.vertices[v].nextarc; T.vertices[v].nextarc=pr1; k++;

-.201.-