图的遍历
这篇文章中总结一下关于图的遍历算法，在此之前，我们来看一下什么是图：
首先，图可以分为有向图和无向图（这里只讨论无权图），像下面这个图就是无向图，V1 ~ V5 是图的顶点，而连接图的两个顶点的线就叫边或者专业一点的说法叫做：“度”，在无向图中，两个顶点之间的连线的方向可以是互换的，比如说，V1 顶点和 V2 顶点之间的边我们可以看做是以 V1 为起点， V2 为终点的一条边，也可以看做是以 V2 位起点， V1 位终点的一条边。由此，一个无向图的度的总数等于这个图中的边的总数的两倍，下面的那个图中一共有 7 条边，因为它是无向图，那么它的度的总数就是 14。
下面来看一下有向图：
有向图和无向图不同，图中的每一条边都是有方向的而且是唯一的，像下面的图中，V1 到 V2 中就只有一条边，方向是从 V1 到 V2 ，V2 到 V3 也只有一条边，方向是从 V2 到 V3。V1 和 V3 之间有两条边，分别是从 V1 到 V3 和 V3 到 V1 ，在这个有向图中度的总数为 4 。
接下来来看一下图的储存方式，我们用什么来储存一个图信息呢？最常用的方法就是通过图的邻接矩阵和邻接表来实现，邻接矩阵顾名思义就是用一个二维数组来储存图的信息，图的顶点数目为二维数组的下标最大值，如果两个顶点之间有边直接相连，那么对应的数组的值就为 1 ， 否则为 0。对于上面的图来说，一共有 7 个顶点，那么我们可以设置一个二维数组 a[7][7]，初始值全部设置为 0，之后根据边的信息将这个二维数组信息补全，比如：V1 顶点和 V2 顶点有一条边，那么 a[0][1] = a[1][0] = 1; （注意这里是无向图，所以正反都要储存），对于其余的边也是一样。那么邻接表呢？邻接表通过储存每一个点的度的信息来保存图的信息，我们先对图的边设置一个结构体来描述一条边（终点、下一条边的结构体信息指针），然后设置一个结构体数组来保存每个顶点的边的信息，比如下面的结构体：
struct Node {
int end;
struct node *next;
};那么只要 next 指针不为空，就证明这个顶点还有边。对于上面的图，我们可以设置一个 7 个元素的结构体数组：Node node[7]; 之后对每一个顶点储存边的信息。
好了，对图有了基本的认识之后，我们来看一下图的遍历，所谓图的遍历，就是根据某种算法来将图中的顶点通过连接的边全部访问一遍。在遍历的算法方面，我们可以有两种选择：深度优先遍历和广度优先遍历，先来看看深度优先遍历：深度优先遍历是利用了栈的原理来对图的顶点进行访问，类似我们之前总结过的深度优先搜索，我们总是通过当前顶点的第一条出边（专业术语是：出度）（边的结束顶点下标最小并且这条边的结束顶点还未被访问过）来访问这条出边的结束顶点，之后对当前顶点做同样的处理，直到所有的顶点都被访问完成。
我们以上面第一张无向图为例，
首先，我们先从 V1 顶点开始访问，然后我们对 V1 顶点的度进行讨论，我们发现顶点 V1 的第一条边的结束顶点 V2 还没有被访问过，
这里为什么选择 V2 而不选择 V4 呢？
因为 V2 是第二个顶点，其作为数组下标肯定比第四个顶点小，而我们每次就是要找出还未被访问过的并且作为数组下标最小的顶点来进行访问。
好了，我们继续对 V2 进行讨论，我们发现 V3 也没被访问过，于是访问 V3 ，接下来是 V4 ，最后是 V5，
于是这个无向图的深度优先遍历的结果就是 V1 --> V2 --> V3 --> V4 --> V5。
来看一张图：
为了拍这张图也是不容易，寝室光线不好，在寝室拍了几次效果都不好，然后跑去阳台拍，结果还把纸弄湿了~
好了，小伙伴们能理解这个过程就可以了，根据这个原理我们可以写出伪代码：
// 对 n 顶点进行访问讨论
void dfs(int n) {
cout << n << " ";
for(int i = 0; i < n; i++) {
if(e[n][i] == 1 && i 顶点还未被访问过) {
标记 i 顶点为已经被访问过
dfs(i); // 继续对 i 顶点进行访问讨论
}
}
}下面我们来看一下广度优先遍历：广度优先遍历算法思想是借助队列来完成的，我们每次对当前顶点的所有的出边（出度）进行讨论，如果某条边的结束顶点还未被访问过，那么就把顶点加入到队列的队尾中，直到当前顶点的所有边都讨论完了，我们再从队列头部取出一个顶点，继续对这个顶点的出边进行讨论，重复这个过程，直到队列为空。
我们还是以上面那个无向图为例，来看一下广度优先遍历：
首先将 V1 顶点加入队列中，然后取出队列头元素，也就是 顶点 V1 ，然后对 V1 顶点的两条出边进行讨论，
我们发现这两条出边的结束顶点 V2 V4 都没有被访问过，
于是，我们把 顶点 V2 和 V4 加入队尾，并且将顶点 V1 出队列（因为已经把 V1 的所有出边都讨论完了），
接下来继续取出队列的头元素，也就是 V2 顶点，之后对它的出边进行讨论并且把没有访问过的对应的顶点加入队尾中，
重复这个过程，直到队列为空。继续看一张笔者画的模拟图（不会 PS是硬伤。。。）：
下面给出广度优先遍历的伪代码：
// 宽度优先遍历，n 为图的顶点个数
void bfs(int n) {
que.push(0); // 将 V1 顶点入队
int s;
while(!que.empty) { // 队列非空的时候继续循环
s = que.fornt; // 输出访问的顶点
cout << s;
que.pop; // 队头元素出队列
for(int i = 0; i < n; i++) { // 对当前顶点的所有边进行讨论
if(e[s][i] == 1 && i 顶点未被访问过) {
que.push(i);
}
}
}
}好了，最后给出完整代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 10010; // 图的顶点最大个数
int e[N][N]; // 储存图信息的邻接矩阵
int book[N]; // 标记顶点是否被访问
// 对第 n 个顶点进行深度优先遍历
void dfs(int n, int sum) {
if(n != 0) { // 输出格式控制
cout << " ";
}
cout << n+1; // 输出顶点信息
for(int i = 0; i < sum; i++) { // 对当前所有的顶点进行讨论
// 如果顶点 i 和顶点 n 之间存在边直接相连，并且顶点 i 未被访问
if(e[n][i] == 1 && book[i] == 0) {
book[i] = 1; // 标记这个顶点已经被访问
dfs(i, sum); // 对这个顶点继续进行深度优先遍历
}
}
}
// 对图进行广度优先遍历
void bfs(int n) {
queue<int> que;
book[0] = 1; // 标记第一个顶点已经被访问
que.push(0);
int s;
while(!que.empty()) {
s = que.front(); // 获取队头元素
que.pop(); // 队头元素出队
if(s != 0) { // 输出格式控制
cout << " ";
}
cout << s+1; // 输出顶点信息
for(int i = 0; i < n; i++) {
// 如果顶点 i 和顶点 n 之间存在边直接相连，并且顶点 i 未被访问
if(e[s][i] == 1 && book[i] == 0) {
book[i] = 1; // 标记这个顶点已经被访问
que.push(i); // 这个顶点入队尾
}
}
}
}
int main() {
int n, m; // 图的顶点个数和边的条数
cin >> n >> m;
int x, y; // 边的开始顶点和结束顶点
for(int i = 0; i < m; i++) {
cin >> x >> y;
e[--x][--y] = e[y][x] = 1; // 因为是无向图，所以要双向储存
}
cout << "深度优先遍历结果：" << endl;
book[0] = 1; // 标记第一个顶点已经被访问
dfs(0, n); // 从第一个顶点开始深度优先遍历
memset(book, 0, sizeof(book)); // 重置访问标记
cout << endl << "广度优先遍历结果：" << endl;
bfs(n);
return 0;
}测试数据和结果：
Good， 和我们模拟得到的结果一样。图的遍历算法是图的基础算法， 也是在很多其他图的算法中经常用得到的算法思想，比如图中两个顶点的最短路，图的最小生成树算法等等。
好了。如果博客中有什么不正确的地方，还请多多指点。如果觉得我写得不错，那么请点个赞支持我吧。
谢谢观看。。。