74DPBAIMC_BM})SFTTM)5DK.png
- 从这道题来看，深度优先搜索遍历这个图：首先从没有走到过的顶点作为起始点，假如从1开始作为起始点，与1相连接的有顶点2.3.5，那么首先尝试访问顶点2，与2相连的顶点且没有访问过的只有顶点4，那么接下来访问顶点4，可是定点4没有未访问过的顶点，所以返回顶点2，顶点2也没没有未访问过的顶点则返回顶点1，与顶点1相连且没有被访问过的有顶点3.5那么就可以访问顶点3，顶点3也没有未访问过的顶点所以返回顶点1，只有顶点5没有被访问过所以访问顶点5，这样就遍历完了整个图，顺序为12435。
- 时间戳：这个顶点是被第几个访问到的。
-
深度优先遍历的主要思想：首先以一个未被访问过的顶点作为起始点v,依次从未访问的邻接点出发对图进行遍历，直到图中和v相连的顶点都被访问到，若图中有未被访问的则从一个未被访问的顶点出发重新进行遍历。
QQ截图20190315202807.png
上图二维数组中的第i行的第j列表示的就是顶点i到顶点j是否有边，1表示有，∞表示没有。
- 用c代码完成遍历：
#include <stdio.h>
int book[100];//数组book用来记录哪些顶点已经访问过
int sum;//用来记录已经访问过多少个顶点
int n;//变量n存储的是图的顶点的总个数
int e[100][100];//二维数组e存储的就是图的边（邻接矩阵）
int main(){
int i,j,m,a,b;//i,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;//自己到自己设为0,即为对角线
else
e[i][j]=999999;//将999999设为正无穷，正无穷表示两个点之间没有边
//读入顶点之间的边
for(i=1;i<=m;i++){
scanf("%d %d",&a,&b);
e[a][b]=1;//代表这两个点之间有边
e[b][a]=1;//因为是无向图，所以需要将e[b][a]也赋为1
}
//从1号定点出发
book[1]=1;//标记1号顶点已访问
dfs(1);//从1号顶点开始遍历
getchar();getchar();
return 0;
}
void dfs(int cur)//cur是当前所在的定点编号（当前正在遍历的顶点）
{
int i;
printf("%d ",cur);
sum++;//每访问一个顶点，sum就加1
if(sum==n)//所有顶点都已经访问过则直接退出
return;
for(i=1;i<=n;i++){//从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
//判断当前顶点cur到顶点i是否有边，并判断顶点i是否已经访问过
if(e[cur][i]==1&&book[i]==0){//等于1 代表有边，等于0代表没有被访问过
book[i]=1;//标记顶点i被访问过
dfs(i);//从顶点i再出发继续遍历
}
}
return;
}
验证时输入：
5 5
1 2
1 3
1 5
2 4
3 5
结果为
1 2 4 3 5
- 用Java代码完成遍历：
import java.util.Scanner;
public class DFS {
static int[] book = new int[100];
static int sum = 0;
static int n;
static int m;
static int[][] e = new int[100][100];
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == j) {
e[i][j] = 0;
} else {
e[i][j] = 999999;
}
}
}
for (int i = 1; i <= m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
e[a][b] = 1;
e[b][a] = 1;
}
book[1] = 1;
dfs(1);
}
public static void dfs(int cur) {
System.out.println(cur + " ");
sum++;
if (sum == n) {
return;
}
for (int i = 1; i <= n; i++) {
if (e[cur][i] == 1 && book[i] == 0) {
book[i] = 1;
dfs(i);
}
}
return;
}
}
特别注意的是：在输入n 和m的时候，不能加int
int n = sc.nextInt();是错的
int m = sc.nextInt();是错的
以上只是一个简单的深度优先搜索例子。
