第7章 图结构
个顶点后，该顶点的标号入队；然后，从队列头部取出一个顶点下标，依次访问该下标所对应顶点的所有未被访问过的邻接点，并依次将各个访问过的邻接点的下标入队，直到队列为空为止。
(1)遍历算法实现
函数void BFSTraverse_ALG(ALGraph G)实现对邻接表表示的图G的广度优先遍历。 void BFSTraverse_ALG(ALGraph G) { int v,w,u,n=G.vexnum; int* Q=new int[G.vexnum]; //定义顶点标号队列Q int front=0,real=0; ArcNode* pr; for(v=0;v (2)主函数调用演示程序 主函数首先建立有向图G1和无向图G2的邻接表，再分别对其进行广度优先遍历并显示输出邻接表和遍历序列。 void main() { ALGraph G1,G2; -.192.- 第7章 图结构 GKind gk1=DG,gk2=UDG; cout<<\建立一个有向图的邻接表G1:\\n\ CreateGraph_AL(G1,gk1); cout<<\建立一个无向图的邻接表G2:\\n\ CreateGraph_AL(G2,gk2); cout<<\有向图G1的邻接表为:\\n\ DisplyAL(G1); cout<<\有向图G1的广度优先遍历序列为:\\n\ BFSTraverse_ALG(G1); cout<<\无向图G2的邻接表为:\\n\ DisplyAL(G2); cout<<\无向图G2的广度优先遍历序列为:\\n\ BFSTraverse_ALG(G2); }程序运行演示结果如下： 建立一个有向图的邻接表G1: 输入顶点数和边(弧)数vexnum arcnum:6 10↙ 按某种顺序输入6个顶点的值: 1 2 3 4 5 6↙ 输入图中10条边(弧)的信息u v: 1 4 1 2 3 5 3 2 4 5 4 2 5 2 5 1 6 5 6 3↙ 建立一个无向图的邻接表G2: 输入顶点数和边(弧)数vexnum arcnum:8 10↙ 按某种顺序输入8个顶点的值: 1 2 3 4 5 6 7 8↙ 输入图中10条边(弧)的信息u v: 1 3 1 2 2 5 2 4 3 7 3 6 8 7 8 6 8 5 8 4↙ 有向图G1的邻接表为: 0 (1): [1] [3] 1 (2): 2 (3): [1] [4] 3 (4): [1] [4] 4 (5): [0] [1] 5 (6): [2] [4] 有向图G1的广度优先遍历序列为: 1 2 4 5 3 6 无向图G2的邻接表为: 0 (1): [1] [2] 1 (2): [3] [4] [0] 2 (3): [5] [6] [0] 3 (4): [7] [1] 4 (5): [7] [1] 5 (6): [7] [2] 6 (7): [7] [2] 7 (8): [3] [4] [5] [6] 无向图G2的广度优先遍历序列为: 1 2 3 4 5 6 7 8 说明： （1）程序运行演示中建立的是图7.8所示的有向图和图7.19所示的无向图的一种邻接表表示：G1、G2。并分别对其进行广度优先遍历，显示输出遍历序列。广度优先算法的时间复杂度与深度优先算法相同。 （2）程序以邻接表中第一个顶点开始对图进行广度优先遍历。如果输入的顶点值序列的顺序不同或输入的边（或弧）的顺序不同，那么得到的广度优先遍历序列也不同。 7.4生成树和最小（代价）生成树 利用图的遍历算法可以求解图的连通性问题，进而可以求得无向图的生成树或生成森林。 7.4.1生成树 1．生成树的概念 -.193.- 第7章 图结构 设G=(V,E)是一个连通的无向图，则从图G中的任一顶点出发，可以访问到G的全部顶点。在对G的遍历过程中，所经过的边集设为T(G)，没有经过的边集设为B(G)，显然有T∪B=E，且T∩B=?。对于图G1=(V,T)，由于V(G1)=V(G)，E(G1)?E(G)，所以G1是G的一个连通子图，且G1中含有G的所有顶点。我们把连通图中的所有顶点加上遍历时经过的所有边所构成的子图称为生成树。显然G1是G的生成树。 说明： (1) 由于具有n个顶点的连通图G中至少有n-1条边，而G的生成树中恰好有n-1条边，所以生成树是连通图的一个极小连通子图。 (2) 若在生成树中任意加上一条边，则必然形成回路。 (3) 一个连通图的生成树不是唯一的，这是由于遍历图时选择的起点不同、遍历的算法不同（深度优先或广度优先）、结点排列次序不同，因而会产生不同的生成树。 例如，图7.20中给出无向图(a)的4种不同的生成树(b)。 (4) 对于不连通的无向图，从任意顶点出发，不能访问到图的所有顶点，只能得到连通分量的生成树。一个图的所有连通分量的生成树组成该图的生成森林。 2．生成树的算法实现 对于连通的无向图，由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度优先生成树。下面给出深度优先生成树（或森林）的算法实现过程。 (1)二叉链表的结点结构 为了用树的孩子兄弟表示法来表示生成树（或森林），下面给出其二叉链表的结构定义。 typedef struct CSNode { VType data; CSNode *firstchild,*nextsibling; }*CSTree; (2)生成树的算法实现 函数void DFSTree(ALGraph &G,int v,CSTree& T)的功能是，从结点v开始对无向连通图G进行深度优先遍历得到深度优先生成树T。 void DFSTree(ALGraph &G,int v,CSTree& T) { ArcNode* p; CSTree q,s=T; int w,first=1; G.vertices[v].flag=1; for(p=G.vertices[v].nextarc;p;p=p->nextarc) -.194.- 第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 ={}开始。重复执行如下操作： 在所有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.- 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《第7章 图结构》习题解答(6)在线全文阅读。
相关推荐：