第7章 图结构

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 4 8 5 6 3 7

说明：

（1）程序运行演示中建立的是图7.8所示的有向图和图7.19所示的无向图的一种邻接表表示G1和G2，并以邻接表中第一个顶点开始分别对其进行深度优先遍历，并显示输出遍历序列。

（2）对同一个图，如果输入的顶点值序列的顺序不同或输入的边（或弧）的顺序不同，那么创建的邻接表也不同，从而得到的深度优先遍历序列也不同。

（3）图的深度优先遍历的时间复杂度取决于图的存储结构。当以邻接矩阵作为图的存储结构时的时间复杂度为O(n2)，当以邻接表作为图的存储结构时的时间复杂度为O(e+n)。

7.3.2图的广度优先搜索

1．广度优先遍历的定义

图的广度优先搜索类似于树的层次遍历，也是图的一种普遍采用的遍历算法。设初始状态是图中的所有顶点均未被访问。广度优先遍历过程如下：

首先访问指定的起始顶点u，再按某种顺序依次访问u的所有未被访问过的邻接点序列：v1,v2,v3,…,vk；然后按照次序v1,v2,v3,…,vk逐个访问其中每个顶点的所有未被访问过的邻接点（按某种顺序），继续以上过程，直到图中所有和初始顶点u有路径相通的顶点均被访问过为止。如果图中还存在与初始顶点u不连通的顶点，则任选一个没被访问过的顶点做起点，重复上述过程，直到图中所有的顶点均被访问过为止。

说明：根据广度优先搜索的定义可知，同一个图，从同一个顶点开始，可以得到多种不同的广度优先遍历序列。所以，图的广度优先遍历序列不唯一。 例如：

(1) 图7.18所示的无向图，从顶点1开始的广度优先遍历序列有以下6种： 1) 1、2、4、3； 2) 1、2、3、4； 3) 1、4、2、3； 4) 1、4、3、2； 5) 1、3、4、2； 6) 1、3、2、4。

(2) 图7.15所示的有向图，从顶点v1开始的广度优先遍历序列有以下2种： 1) v1，v2，v3，v4； 2) v1，v3，v2，v4。 (3) 图7.19所示的无向图，从顶点1开始，按顶点编号递增顺序进行广度优先遍历的序列为：

1、2、3、4、5、6、7、8。

从顶点1开始，按顶点编号递减顺序进行广度优先遍历的序列为：

1、3、2、7、6、5、4、8。

2．广度优先遍历的算法实现

和深度优先算法类似，在遍历的过程中也需要访问邻接表G的标志数组G.vertices[v].flag，另外还需要一个队列Q来存放已被访问的顶点的标号。在图的某个连通分量中，当访问了一

-.191.-

第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;vadjvex; if(!G.vertices[u].flag) { G.vertices[u].flag=1; //修改标志 cout<nextarc; //进入下一个邻接点 }//end while }//end while }//end if }//end for cout<

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