引入
前面我们已经学过了深度和广度搜索。为什么叫深度和广度呢？其实是针对图的遍历而言的，请看下面这个图：
图是由一些小圆点（称为顶点） 和 连接这些点的直线 （称为边）组成的。
例如上图就是由5个顶点（编号为 1,2,3,4,5） 和5条边（1-2,1-3,1-4,2-4）组成。
现在我们从1号顶点开始遍历这个图，遍历就是把图的每一个顶点都访问一次。使用深度优先搜索将会得到如下的结果。
图中每个顶点旁边的数表示这个顶点是第几个被访问到的，我们称之为 —— 时间戳
使用深度优先搜索来遍历这个图的过程：
首先从一个未走过的顶点作为起始顶点，比如以1号顶点作为起点。沿1号顶点的边去尝试其他它未走过的顶点，首先发现的是2号顶点还没被走过，于是来到了2号顶点。
再以2号顶点作为出发点继续尝试访问其他未走到过的顶点，这样又来到了4号顶点。
再以4号顶点作为出发点继续尝试访问其他未走过的顶点。但是，此时在4号顶点的周围已经没有其他的顶点了，所以需要返回到2号顶点。返回到2号顶点后，发现沿2号顶点也不能在访问到其他未走到的点了，此时又需要返回到1号顶点。
继续以1号顶点尝试访问其他顶点，我们来到了3号点。以此类推，我们最后来到了5号点。到此，所以的顶点都走过了，遍历结束
深度优先搜索的主要思想是：
首先以一个未被访问的顶点作为起始顶点，沿当前顶点的边走到未被访问过的顶点
当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问过。
显然，深度优先搜索是沿着图的某一条分支遍历直至末端，然后回溯，再沿另一条实现相同的遍历，直到所以的顶点都被访问完为止。
代码实现
上面的二维数组中 第i行第j列就是表示顶点i到顶点j是否有边。
1表示有边，x表示没有边，0表示顶点自己到自己。
我们将这种方法称为 —— 图的邻接矩阵储存法。
细心的朋友可能会发现这张图沿着对角线全部是0，因为上面这张图是 无向图。
所谓无向图就是指图的边没有方向。例如边 1 - 5 表示 1号顶点可以到 5号顶点，5号顶点也可以到1号顶点。
接下来就是解决怎么用深度优先搜索来实现遍历了：
voiddfs(intcur) //cur是当前所在的顶点编号 { printf("%d", cur); sum++; //每访问一个点就sum++ if (sum == n) return; //所有的顶点都访问过了 for (i = 1; i <= n; i++) //从1到n的顶点依次尝试，看看有哪些顶点与当前顶点cur有边相连 { //判断当前顶点cur到顶点i是否有边，并判断顶点i是否已被访问过 { if (e[cur][i] == 1 && book[i] == 0) { book[i] = 1; //标记顶点i已经访问过 dfs(i); //从顶点i出发继续遍历 } } } return; }
在上面的代码中 变量 cur 存储的是当前正在遍历的点，二维数组e存储的就是图的边（邻接矩阵），数组book用来标记哪些顶点已经访问过，变量sum用来记录已经访问多少个顶点，变量你存储的是图的顶点总个数。
完整代码
#include <stdio.h> intbook[101], sum, n, e[101][101]; voiddfs(intcur) //cur是当前所在的顶点编号 { printf("%d", cur); sum++; //每访问一个点就sum++ if (sum == n) return; //所有的顶点都访问过了 for (i = 1; i <= n; i++) //从1到n的顶点依次尝试，看看有哪些顶点与当前顶点cur有边相连 { //判断当前顶点cur到顶点i是否有边，并判断顶点i是否已被访问过 { if (e[cur][i] == 1 && book[i] == 0) { book[i] = 1; //标记顶点i已经访问过 dfs(i); //从顶点i出发继续遍历 } } } return; } intmain() { inti, j, m, a, b; scanf("%d %d", &n, &m); //初始化二维矩阵 for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) if (i == j) e[i][j] = 0; elsee[i][j] = 99999999; //我们假设99999999为x //读入顶点之间的边 for (i = 1; i <= n; i++) { scanf("%d %d", &a, &b); e[a][b] = 1; e[b][a] = 1; //因为该图为无向图 } //从1号顶点出发 book[1] = 1; //标记1号顶点已经访问 dfs(1); //从1号顶点开始遍历 return0; }
如果觉得有什么意见或者是需要的话，欢迎在评论区向小玄提出哦！
