数据结构 - 图（遍历）

2020-10-03 本文已影响0人 Whyn

图的遍历和树的遍历类似，我们希望 从图中某一顶点出发，遍历图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

树常用的遍历方式有四种方案：前序遍历，中序遍历、后序遍历和层序遍历。但是无论是采用哪种遍历方式，它都有一个明确的起点位置，即根结点，且所有的子结点都只有一个双亲结点，这种遍历的路径很明确。

而对于图的遍历，由于图中所有顶点地位相等，因此可以从任意一个顶点开始进行遍历，更加致命的是，图中顶点间的关系错综复杂，每几个顶点之间就可能形成一个环，这样有可能导致图的遍历存在死循环，无法遍历到其他顶点。所以通常需要额外提供一个访问数组visited[n]来对遍历过程中已遍历的顶点进行一个标记，避免重复访问。visited[n]数组中，n是图中顶点个数，初始值为0（或false），表示顶点未访问，当遍历访问该顶点后，就将其设置为1（或true），作为顶点已访问标记。

图的遍历通常有两种方案：深度优先遍历 和 广度优先遍历。

深度优先遍历（Depth First Search）：也称为 深度优先搜索，简称 DFS。对于连通图，它从图中某个顶点 $v$ 触发，访问此顶点，然后从 $v$ 的未被访问的邻接点出发深度优先遍历图，直至图中所有和 $v$ 有路径相通的顶点都被访问到。而对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚未有顶点未被访问（从visited[n]数组得知：若visited[i] == false，则顶点 $v_i$ 未被访问），则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。（所谓深度优先搜索，就是选择一个顶点开始走，期间对于走过的顶点就不再访问，走其他未被访问的，一直走到无路可走。若此时还有顶点未走过，选择一个，重复上述过程。）。

深度优先遍历的过程类似与树的前序遍历，比如对于下图：
深度优先遍历
上图左图为原始图，右图为左图采用深度优先遍历得到的路径图，可以看到有图非常类似树的前序遍历结果。

下面对上图左侧原始图采用深度优先遍历的整个具体过程做简要介绍：
1. 假设我们从顶点 $A$ 开始进行遍历，且当遇到多条路径时，默认采用向右行走原则。
2. 首先访问顶点 $A$ ，此时设置visited[0] = true，表示已访问（后续访问其他顶点时，默认同样设置visited数组，后面内容就不加以赘述了），然后 $A$ 有两条路径可选择，这里选择走右边路径，即顶点 $B$ 。
3. $B$ 访问完成后，又有三条路径可走： $C$ 、 $I$ 和 $G$ ，同样，选择右侧路径 $C$ ...
4. 就这样我们一直往右侧方向顶点进行遍历，整个过程参考上图右侧路径，一直走到顶点 $F$ 处，此时我们依旧选择右侧顶点，即 $A$ ，但是由于 $A$ 已被访问过，无需再遍历，因此回退到顶点 $F$ ，选择右侧第二条路径，即顶点 $G$ 。
5. 访问完顶点 $G$ 后，又有三条路径可选： $B$ 、 $D$ 和 $H$ ，由于 $B$ 和 $D$ 都已被访问过，所以这里直接走顶点 $H$ 。
6. 访问完顶点 $H$ 后，有两条路径可选： $D$ 和 $E$ ，但是这两个顶点都被访问过，这样一轮遍历其实已经到底了（最深处），但是图中可能还存在其他未被遍历的顶点，因此，这里我们需要执行回退。
7. 我们回退顶点 $H$ 处，发现所有路径都走过，因此再回退到顶点 $G$ ，发现也是所有路径都走过，继续回退到顶点 $F$ ，也全部都访问过...一直回退到顶点 $D$ ，发现顶点 $I$ 没有被访问过，于是访问顶点 $I$ 。
8. 访问完顶点 $I$ 后，发现所有路径都访问过，因此继续回退： $I$ -> $C$ -> $B$ -> $A$ ，最终回退到了顶点 $A$ ，也就是我们的开始遍历的地方，此时就表示深度遍历已完成，图中所有的顶点都已被遍历过。
深度优先遍历的代码实现如下所示：
注：由于遍历是对顶点进行访问（对顶点进行操作），所以图的结构使用邻接矩阵或者邻接表比较合适，这两种结构实现都差不多，这里我们采用邻接矩阵进行实现。
```
// 头文件
#ifndef __MGRAPH_H__
#define __MGRAPH_H__


#define MAX_VEX  100                   // 最大顶点数
#define WEIGHT_INFINITY 65535          // 无效权值，用 65535 表示正无穷

/*
* V：表示顶点 Vertext 类型
* E：表示边权值类型
*/
template<typename V, typename E>
struct MGraph {                        // 邻接矩阵
    V vexs[MAX_VEX];                   // 顶点数组（顶点表）
    E arc[MAX_VEX][MAX_VEX];           // 邻接矩阵（边表）
    int numsVertex = 0, numsEdge = 0;  // 图中顶点数和边数

    bool visited[MAX_VEX] = { false };
    void DFSTraverse();                // 深度优先遍历
    void DFS(const int i);             // 递归访问顶点Vi
};
#endif

// 源文件
#include "MGraph.h"
#include <iostream>
using namespace std;

template<typename V, typename E>
void MGraph<V, E>::DFSTraverse() {
    // 初始所有顶点状态为未访问
    for (int i = 0; i < this->numsVertex; ++i) {
        this->visited[i] = false;
    }

    // 非连通图，不同的连通分量要单独进行 DFS
    for (int i = 0; i < this->numsVertex; ++i) {
        // 当前顶点未被访问，深度递归进行访问
        // 对于连通图，只需执行一次
        if (!this->visited[i]) {
            DFS(i);
        }
    }
}

template<typename V, typename E>
void MGraph<V, E>::DFS(const int i) {
    // 标识当前顶点已被访问
    this->visited[i] = true;
    // 打印当前顶点，表示已对当前顶点进行操作
    cout << this->vexs[i] << endl;
    for (int j = 0; j < this->numsVertex; ++j) {
        // 如果邻接点存在且未被访问，则对其进行 DFS
        if (this->arc[i][j] == 1 && !this->visited[j]) {
            DFS(j);
        }
    }
}
```

广度优先遍历（Breadth First Search）：又称为 广度优先搜索，简称 BFS。广度优先遍历类似于树的层序遍历，即从图中的某一个顶点出发，遍历一个顶点时，依次遍历其所有的邻接点，邻接点全部遍历完成后，就从邻接点出发，同样依次遍历它们的邻接点...直至遍历结束。

同样以上图深度遍历采用的原始图进行讲解，将其图稍微进行变形，如下所示：

广度优先遍历

下面针对上图右侧图介绍广度优先遍历的具体过程：

广度优先遍历通常借助队列来实现遍历，假设我们从顶点 $A$ 开始进行遍历
首先访问顶点 $A$ ，此时设置visited[0] = true，表示已访问（后续访问其他顶点时，默认同样设置visited数组，后面内容就不加以赘述了），然后将顶点 $A$ 压入队列。
对队列进行判断，如果非空，就取出队列第一个数据，也即顶点 $A$ ，然后获取顶点 $A$ 的所有邻接点，依次压入队列中。此时顶点 $B$ 和 $F$ 就会被压入队列中。
对队列进行判断，如果非空，就重复步骤3，也即取出队列头部数据，将其所有邻接点压入队列中...如此重复操作，直至队列为空。

上述操作过具体过程如下图所示：

广度优先遍历：实现过程

广度优先遍历的代码实现如下所示：
注：下面代码仍以邻接矩阵表示图结构。

// 头文件
#ifndef __MGRAPH_H__
#define __MGRAPH_H__


#define MAX_VEX  100                   // 最大顶点数
#define WEIGHT_INFINITY 65535          // 无效权值，用 65535 表示正无穷

/*
* V：表示顶点 Vertext 类型
* E：表示边权值类型
*/
template<typename V, typename E>
struct MGraph {                        // 邻接矩阵
    V vexs[MAX_VEX];                   // 顶点数组（顶点表）
    E arc[MAX_VEX][MAX_VEX];           // 邻接矩阵（边表）
    int numsVertex = 0, numsEdge = 0;  // 图中顶点数和边数

    bool visited[MAX_VEX] = { false };
                                       // ...

    void BFSTraverse();                // 广度优先遍历
    void BFS(const int i);             // 对顶点Vi进行广度优先遍历
} ;
#endif

// 源文件
#include "MGraph.h"
#include <iostream>
#include <queue>

using namespace std;
// ...

template<typename V, typename E>
void MGraph<V, E>::BFSTraverse() {
    // 初始所有顶点状态为未访问
    for (int i = 0; i < this->numsVertex; ++i) {
        this->visited[i] = false;
    }

    // 对所有未访问过的顶点进行广度优先遍历
    for (int i = 0; i < this->numsVertex; ++i) {
        if (!this->visited[i]) {
            BFS(i);
        }
    }
}

template<typename V, typename E>
void MGraph<V, E>::BFS(const int i) {
    // 表示队列头元素对应的顶点表下标
    int cur = i;
    this->visited[cur] = true;
    // 访问当前顶点（这里直接输出）
    cout << this->vexs[cur] << endl;
    // 创建一个队列
    std::queue<V> vertexQueue;
    // 将当前顶点下标压入队列
    vertexQueue.push(cur);
    // 队列不为空
    while (!vertexQueue.empty()) {
        // 弹出队列头部元素，并获取其下标
        cur = vertexQueue.front();
        vertexQueue.pop();
        // 遍历所有顶点，找到未访问过的邻接点
        for (int j = 0; j < this->numsVertex; ++j) {
            // 如果邻接点存在且未被访问
            if (this->arc[cur][j] == 1 && !this->visited[j]) {
                // 访问邻接点（这里直接输出）
                cout << this->vexs[j] << endl;
                // 设置邻接点已访问
                this->visited[j] = true;
                // 将邻接点压入队列
                vertexQueue.push(j);
            }
        }
    }
}

深度优先遍历与广度优先遍历算法在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同。

深度优先遍历可以认为是纵向遍历图，而广度优先遍历则是横向进行遍历。

深度优先和广度优先两者并无优劣之分，应依据不同的情况酌情选择：

深度优先更适合目标比较明确，以找到目标为主要目的的情况。
广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

数据结构 - 图（遍历）

参考

猜你喜欢

热点阅读