第7章 图结构

函数void DisplyAMLG(AMLGraph G)按邻接表的方式显示当前邻接多重链表表示的无向图G的相关信息。

void DisplyAMLG(AMLGraph G) { int i; EBox* p; cout<<\按邻接表显示结果为：\\n\ for(i=0;iivex==i) cout<<'['<ivex<<' '<jvex; else cout<<'['<jvex<<' '<ivex; if(G.kind==DN)cout<<' '<info; cout<<\ if(p->ivex==i) p=p->ilink; //指针指向下一个边结点 else p=p->jlink; } cout<

程序中分别建立一个无向图(G1)和一个无向网(G2)的邻接多重链表，并按邻接表的形式显示所建立的的邻接多重链表的内容。

void main()

{ AMLGraph G1,G2; GKind gk1=DG,gk2=DN; cout<<\建立一个无向图的邻接多重链表G1:\\n\ CreateGraph_AMLG(G1,gk1); cout<<\建立一个无向网的邻接多重链表G2:\\n\ CreateGraph_AMLG(G2,gk2); cout<<\无向图G1的信息为:\\n\ DisplyAMLG(G1); cout<<\无向网G2的信息为:\\n\ DisplyAMLG(G2); }程序运行演示结果为：

建立一个无向图的邻接多重链表G1:

输入顶点数和边数vexnum edgenum:4 5↙ 按某种顺序输入4个顶点的值: 1 2 3 4↙

输入图中5条边的信息u v: 1 2 1 3 1 4 2 3 2 4↙

建立一个无向网的邻接多重链表G2:

输入顶点数和边数vexnum edgenum:4 5↙

-.187.-

第7章 图结构

按某种顺序输入4个顶点的值: 1 2 3 4↙

输入图中5条边和权的信息u v w: 1 2 3 1 3 6 1 4 4 2 3 5 2 4 8↙ 无向图G1的信息为: 按邻接表显示结果为： 0 (1): [0 3] [0 2] [0 1] 1 (2): [1 3] [1 2] [1 0]

2 (3): [2 1] [2 0] 3 (4): [3 1] [3 0]

无向网G2的信息为: 按邻接表显示结果为： 0 (1): [0 3 4] [0 2 6] [0 1 3] 1 (2): [1 3 8] [1 2 5] [1 0 3] 2 (3): [2 1 5] [2 0 6] 3 (4): [3 1 8] [3 0 4]

说明：

（1）程序演示中所建立的是图7.18中无向图(a)和无向网(b)的邻接多重链表的一种表示。

（2）从存储结构可以看出，在邻接多重结构存储的链表中很容易算出一个顶点的度，并且建立邻接多重链表的时间复杂度与建立邻接表的时间复杂度相同，所以在无向图（或网）的应用中，常常用邻接多重链表作为存储结构。

7.3图的遍历

从图中某一顶点出发，访问图中其余各顶点，而且每个顶点仅被访问一次的过程称为图的遍历。图的遍历算法是图的诸多应用中的基础，例如求解图的连通性、生成树、拓扑排序、关键路径等问题中都是以图的遍历算法为基础。

图的遍历比树的遍历要复杂得多，因为图中任意两个顶点之间都可能有边（或弧）存在，所以在访问了某个顶点之后，可能沿着某个路径又回到该顶点上，由此可能导致某个顶点在遍历的过程中被访问多次。为了保证在遍历过程中每个顶点仅被访问一次，必须记下已访问过的顶点。通常需要设立一个一维数组visited[]，其中每个元素对应图中某个顶点被访问的次数，遍历前它们的值均为0，表示相应的顶点未被访问过，一旦该顶点被访问则数组visited中相应的元素值变为1。为了方便起见，我们在图的邻接矩阵和邻接表存储的顶点序列vexs[]（邻接矩阵）和vertices[]（邻接表）中均增设了用于表示该顶点是否被访问过的标志域flag。

图的遍历算法通常有深度优先搜索(depth first search)和广度度优先搜索(breadth first search)两种。

7.3.1图的深度优先搜索

1．深度优先遍历的定义

图的深度优先搜索类似于树的先根遍历，是树的先根遍历的推广。设初始状态是图中的所有顶点均未被访问。深度优先遍历过程为：

首先访问指定的起始顶点u，然后选取与u邻接的未被访问的任一顶点v访问之，再选取与v邻接的未被访问的任一顶点w访问之。重复进行以上访问过程，当到达一个所有邻接顶

-.188.-

第7章 图结构

点都被访问过的顶点时，则依次退回到最近被访问过的顶点。若它还有邻接的顶点未被访问过，则从这些未被访问过的顶点中任意选取一个顶点，重复上述过程，直到所有的顶点都被访问过为止。 说明：

(1) 图的深度优先搜索法的遍历过程是一个递归过程；

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

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

(2) 图7.11(b)所示的无向图，从顶点v1开始的深度优先遍历序列有以下5种： 1) v1，v2，v5，v3，v4；2) v1，v2，v5，v4，v3；3) v1，v3，v4，v5，v2； 4) v1，v3，v5，v2，v4；5) v1，v3，v5，v4，v2。

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

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

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

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

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

深度优先算法，在遍历的过程中需要访问邻接表G的标志数组G.vertices[v].flag，顶点一旦被访问则其相应的标志由0修改为1。 (1)对连通分量的深度优先遍历

函数void DFS_ALG(ALGraph &G,int v)的功能是，对以邻接表方式存储的图G，从顶点编号为v的顶点开始，用递归的方式，深度优先遍历该顶点所在的连通分量。

void DFS_ALG(ALGraph &G,int v) { int w; ArcNode* p; cout<nextarc) //进入下一层 { w=p-> adjvex;

-.189.-

第7章 图结构

}

}

if(!G.vertices[w].flag)DFS_ALG(G,w); //通过递归调用实现深度优先遍历

(2)对图的深度优先遍历

函数void DFSTraverse_ALG(ALGraph G)的功能是，通过重复调用函数DFS_ALG(G,v)实现对邻接表G的深度优先遍历。

void DFSTraverse_ALG(ALGraph G) { int v; for(v=0;v

主函数首先建立有向图G1和无向图G2的邻接表，再分别对其进行深度优先遍历并显示输出邻接表和遍历序列。

void main()

{ ALGraph G1,G2; 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\ DFSTraverse_ALG(G1); cout<<\无向图G2的邻接表为:\\n\ DisplyAL(G2);

cout<<\无向图G2的深度优先遍历序列为:\\n\ DFSTraverse_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的深度优先遍历序列为:

-.190.-