第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
(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.- 第7章 图结构 } for(j=0;j (4) 主函数演示程序void main() 主函数首先建立一个无向网的邻接矩阵G，并显示输出该矩阵，然后通过克鲁斯卡尔算法得到以邻接表存储的最小生成树T，最后显示输出T中所有弧的相关信息。 void main() { MGraph G; ALGraph T; GKind gk=UDN; cout<<\建立一个无向网的邻接矩阵G:\\n\ CreateGraph_MG(G,gk); cout<<\无向网G的邻接矩阵为:\\n\ DisplyMG(G); //显示G的邻接矩阵 MiniTree_Kruskal(T,G); cout<<\无向网G的最小生成树的邻接表为:\\n\ DisplyAL(T); //显示T的邻接表 }程序运行演示结果为： 建立一个无向网的邻接矩阵G: 输入顶点数vexnum和弧数arcnum:7 12↙ 按某种顺序输入7个顶点的值: 1 2 3 4 5 6 7↙ 输入图中12条边(弧)和权的信息u v w: 1 2 2 2 5 10 5 7 6 7 6 1 6 3 5 3 1 4 4 1 1 4 2 3 4 5 7 4 7 4 4 6 8 4 3 2↙ 无向网G的邻接矩阵为: 0 2 4 1 0 0 0 2 0 0 3 10 0 0 4 0 0 2 0 5 0 1 3 2 0 7 8 4 0 10 0 7 0 0 6 0 0 5 8 0 0 1 0 0 0 4 6 1 0 无向网G的最小生成树的邻接表为: 0 (1): [1,2] [3,1] 1 (2): [0,2] 2 (3): [3,2] 3 (4): [6,4] [2,2] [0,1] 4 (5): [6,6] 5 (6): [6,1] 6 (7): [4,6] [3,4] [5,1] 说明： （1）程序运行中所建立的是图7.21(a)所示的无向网G的邻接矩阵，其输出结果是图7.21(b)所示的最小生成树T的邻接表。在T的显示列表中，第1列为结点下标，第2列为结点值，以后的每一项为[邻接点,权值]。 （2）克鲁斯卡尔算法的时间复杂度为O(e*loge)，其中e为无向连通网G的边数。因此，相对于普里姆算法而言，它更适合于求稀疏网的最小生成树问题。 7.5最短路径 在有向网中求解最短路径(shortest path)是一个很有实际应用价值的问题。例如，交通网络可以看成是带权值的图，图中的顶点表示城市，边表示城市之间的交通线，边上的权值表示交通线的长度或花费代价。对这样的交通网络，常常会关心如下问题： （1）从A城市到B城市是否有公路可通？ -.202.-