数据结构--图的遍历（二）

ゝ一世哀愁。 2022-06-05 12:27 210阅读 0赞

图的遍历是指，从图中某一个顶点开始，访问且仅访问图中结点一次，分为深度优先遍历和广度优先遍历，两种遍历方法分别类似树的先根遍历和层序遍历

为了能够对图中所有节点进行访问且仅访问一次，我们需要考虑虾下面几个问题：  
1. 不同于树，对于一个图而言，图中结点是没有收尾之分的，所以需要我们指定一个要访问的第一个结点。  
2. 在遍历结点的过程中，可能会有回路，造成死循环  
3. 一个结点通常和若干个节点邻接，要保证一个结点所有的邻接结点按照某种次序都被访问到

下面具体介绍两种遍历方法：

## 1.深度优先遍历 ##

**算法思想：**对于图中所有未被访问的结点，从某个顶点v出发，访问顶点，然后对顶点的邻接点进行深度优先遍历。即，每次访问当前结点后，首先访问当前结点的第一个邻接结点，递归。通俗点儿说，对于一个结点，找到他的一个未被访问的邻接点就继续找邻接点的邻接点，直到当前被访问的点没有邻接点，然后在回过头来继续找没有被访问过的结点，找邻接……

**算法过程**

1.  访问节点v，标记为已访问
2.  查找v的未被访问的第一个邻接结点w
3.  若w存在，则继续执行；否则算法结束
4.  若w尚未被访问，则深度优先搜索w
5.  查找v的w邻接结点的下一个邻接结点w，转到3

**示例**  
![这里写图片描述][SouthEast]

**结果**

A->B->E->G->C->F->D->H->I

## 2.广度优先遍历 ##

这里不写严谨的理论，我们可以根据字面意思来理解。在广度优先遍历中，会先访问A的一层所有邻居，然后是所有的二层邻居、所有三层邻居……，一层全部被访问之后采取访问下一层的结点。也就是所谓的“广度”优先。

那么，如何让程序去执行这个过程呢？类似二叉树的层序遍历，用一个队列保持访问过的结点的顺序，然后按照这个顺序来访问这些节点的邻接节点。个人认为，类似这种思想的重点是要想好，把谁入队列/栈，什么时候入队/栈，什么时候出队/栈。

**算法过程**

1.  访问结点v，标为已访问
2.  把v入队列
3.  队列非空时继续，否则结束
4.  出队列取得队头结点u
5.  找u的第一个邻接点w
6.  如果u的邻接点w不存在，则转3，否则循环如下：  
    
    
     *  如果w未被访问，则访问w，并标记为已经访问
     *  w入队列
     *  找u的w邻接后的下一个邻接点w，转到6

**示例：**

![这里写图片描述][SouthEast 1]

我们可以这样理解这个过程，比如节点A有3个邻居，因为是广度优先，所以我们会先探测A的所有邻接结点，对于没有跟A直接邻接的节点，我们会在访问完A的直接邻接（也就是上面提到的第一层）之后再去访问，对于剩余节点的访问也需要一个顺序，首先访问B的邻居，然后是C的邻居，D的邻居。由于当前不访问，而是过会儿再访问，同时还要保证B的邻居、C的邻居、D的邻居的顺序访问，这符合队列“先进先出”的思想。所以我们采用队列存储。

**结果：**  
A->B->C->D->E->F->G->H->I

[SouthEast]: /images/20220605/9ad8f2d46f5442c1a801e759e5c3dd69.png
[SouthEast 1]: /images/20220605/6a22244ed90a4afe902c5e50ad90a004.png