扫码获取更多资源

●图的遍历

在ADT Graph定义的基本操作中，最基本的操作就是图的遍历。它是指从图中某一 顶点出发，对图中所有顶点访问一次且仅访问一次。由于图结构本身的复杂性，所以图的遍 历操作也比较复杂。首先解决以下四个问题：

(1)图中没有一个确定的开始顶点，任意一个顶点都可以作为遍历的起始顶点，那么应 该如何选取遍历的起始顶点？

解决：可以从图中任一顶点出发，不妨按照编号的顺序，先从编号小的顶点开始。

(2)图中从某个顶点出发可能到达不了所有其他顶点，例如非连通图，从一个顶点岀 发，只能访问它所在的连通分量上的所有顶点，那么应该如何才能遍历图的所有顶点？

解决：多次调用从某一顶点出发遍历图的操作即可。

(3)图中由于存在回路,某些顶点可能会被重复访问，那么应该如何避免遍历不会因回 路而陷入死循环？

解决：可以设置一个访问标志数组visited[n],n为图中顶点个数，其初值为未被访问 标志“0”，如果某顶点已被访问，则将该顶点的访问标志设为“1”。

(4)图中一个顶点可以和其他多个顶点相邻接，当这样的顶点访问过后，应该如何选取 下一个要访问的顶点？

解决：这属于遍历次序的问题。图的遍历通常有深度优先遍历(Depth-First Search, DFS)和广度优先遍历(Breadth-First Search ,BFS)两种方式，这两种遍历次序对无向图和 有向图都适用。

1.深度优先遍历

定义：①从图中某顶点v出发，访问顶点v；

②从V的未被访问的邻接点中选取一个顶点W,从W出发进行深度优先遍历；

③重复上述两步，直至图中所有和V有路径相通的顶点都被访问到。

方法：深度优先遍历是一个递归过程，因此采用递归方法完成操作。图的深度优先遍 历类似于树的先序遍历。

定义：图7-10(b)给岀了对于图7-10(a)所示的无向图，从顶点V|出发进行深度优先遍历的一 种路线，图7-10(c)给出了在递归执行过程中栈的变化情况。得到深度优先遍历序列为V】 V2 v5 v3 v4 V6 ,在遍历过程中的岀栈序列为v5 v4 v3 v2 V6 Vi。

广度优先遍历

定义：①从图中某顶点V出发，访问顶点V；

②依次访问V的各个未被访问的邻接点V1 , V2，…，Vk ;

图的存储表示与操作实现

图的复杂性表现在不仅各个顶点的度可以相差很多，而且顶点之间的逻辑关系也错综 复杂。图的存储表示除了要求能存储各顶点的数据信息，还要求能唯一反映图中各顶点之 间的逻辑关系。

由于图中任意两个顶点之间都可能存在关系，无法以顶点在存储区中的物理位置来表 示元素之间的逻辑关系，因此很难使用顺序存储结构，但是可以借助二维数组的数据类型表 示元素之间的关系。另外，如果用多重链表表示图，即由一个数据域和多个指针域组成的结 点表示图中的一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针, 则是一种最简便的链式存储结构。但由于图中各顶点的度各不相同，最大度数和最小度数

可能相差很多，因此若按最大度数设计结点结构则造成存储空间的浪费，若按顶点度数设计 结点结构则造成算法设计的困难。因此，和树类似，在实际应用中不适宜釆用这种结构，而 应该根据具体的图和需要进行的操作，设计适当的结点结构和表结构。图常用的存储结构 有邻接矩阵、邻接表、十字链表和邻接多重表。为了适合用C语言描述，以下假定顶点序号 (位置)从0开始，即图G顶点集的一般形式是V(G) = {V。，Vi ,vn_!} o

联系我们：