第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;v
显然,该算法的时间复杂度与深度优先遍历算法的时间复杂度相同。
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 ={}开始。重复执行