第7章 图结构

}

{ w=p->adjvex; if(!G.vertices[w].flag) { q=new CSNode; //动态分配结点q q->data=G.vertices[w].data; //为结点q赋值 q->firstchild=q->nextsibling=NULL; if(first){ first=0; T->firstchild=q; } //w是第一个v的未被访问的邻接点 else{ s->nextsibling=q; s=q; } //w是v的其它未被访问的邻接点 DFSTree(G,w,q); //从w出发深度优先遍历G，建立子生成树q }//end_if }//end_for

(3)生成森林的算法实现

函数void DFSForest(ALGraph G,CSTree& T)的功能是，从无向图G的第一个结点（按邻接表中的结点顺序）开始，对G进行深度优先遍历得到深度优先生成森林（或树）T。

void DFSForest(ALGraph G,CSTree& T) { CSTree p,q; int v; T=NULL; for(v=0;vdata=G.vertices[v].data; //为结点p赋值 p->firstchild=p->nextsibling=NULL; if(!T)T=q=p; //v是第一棵生成树的根 else{ q->nextsibling=p; q=p;} //v是其它生成树的根 DFSTree(G,v,p); //建立以p为根的生成树 } }

显然，该算法的时间复杂度与深度优先遍历算法的时间复杂度相同。

7.4.2最小（代价）生成树

1．最小生成树的概念

对于无向网，因为它的边是带有权值的，而一个图的生成树是不唯一的，那么，就产生了这样一个问题：如何找到一个各边的权值总和最小的生成树，这种生成树称为最小（代价）生成树。最小生成树问题在实际应用中很有意义，比如，要在n个城市之间建立通信联络网，最多有n(n-1)/2条路线，而连通这n个城市仅需要其中的n-1条路线（图的生成树）即可，由于每对城市之间的距离不一样，铺设线路所花费的经济价格也不一同，此时，自然会考虑到

-.195.-

第7章 图结构

如何在最节省经费（最小代价）的前提下建立通信网。

例如，图7.21(b)是图7.21(a)的最小生成树。

常用的最小代价生成树算法有两种，即普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。这两种算法都用了最小生成树的MST性质，即：设N=(V,VR)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必有一棵包含边(u,v)的最小生成树。

2．普里姆(Prim)算法 (1)普利姆算法思想

设N=(V,VR)是一个连通网，TE 是V上最小生成树边的集合。普里姆（Prim）算法从U={u0}(u0∈V)，TE ={}开始。重复执行如下操作：

在所有u∈U，v∈V-U的边(u,v)∈VR中找一条代价最小的边(u0,v0)并入集合TE，同时v0

并入U，直至U=V为止。此时TE中必有n-1条边，则T=(U,TE)为网N=(V,VR)的最小生成树。

例如，对于图7.21(a)所示的网，从顶点1开始，按照普里姆算法求最小生成树的过程，可以由图7.22(a)到图7.22(f)表示。

为了便于普里姆算法的实现，还需要附设一个数组closedge[]，用以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在数组中存在相应的元素closedge[i-1]，它包含两个域：一个是adjvex域，用于存储该边所依附的在U中的点；另一个是lowcost域，用于存储该边

-.196.-

第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.-