图的搜索(遍历) - BFS & DFS
source link: https://blog.ixk.me/post/graph-search-bfs-dfs
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
BFS，即 Breath First Search（广度优先搜索）
DFS，即 Deep First Search （深度优先搜索）
图的搜索是对于连通图的一种遍历策略，常用于走迷宫的问题
本文的算法基于 C 语言编写，过几天会使用 Java 重写这两个算法
另外本文的算法是对基于数组的图进行搜索，基于链表的搜索暂时未弄 （逃
1.BFS
广度优先搜索顾名思义，就是在广范围进行搜索，从一个顶点 V0 开始，辐射状地优先遍历其周围较广的区域
算法的基本思路
在广搜中不需要记录节点是否走过，但是要记录上一个节点的位置，若将整个过程画成树，即可观察到广搜是一层一层进行遍历的（这里就不画图了，逃），这时若要搜索下一层节点就需要读取上一层节点的位置，并对父节点的所有节点逐个进行搜索，将符合要求的子节点逐个存入下一层节点，直到判断到达终点即停止搜索
基础算法采用递归，存储搜索各层节点采用队列，但由于 C 语言中没有队列所以采用结构体数组代替，使用二维结构体数组，其中一维对应层数，另一维存储该层的节点，另外若要使广搜拥有寻迹功能，即可以输出行进路程中每一步，就需要在结构体中增加一个结构体指针指向父节点，然后记录最后一个节点的地址，通过访问指针来访问父节点，直到到达起点
算法的实现
1#include <stdio.h>
2//广度优先搜索 - 可寻迹
3
4//地图数组
5int map[100][100];
6//地图的个数
7int n;
8//定义起点和终点
9int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;
10//能到达终点的最后一个节点的指针
11struct POINT *end_p = NULL;
12//步进存储结构体
13struct POINT
14{
15 int x; //X轴坐标
16 int y; //Y轴坐标
17 int is = 0; //是否是达到需求的节点，作为下一轮搜索的索引
18 struct POINT *prev;
19} po[100][100]; //po[轮数][不同节点存储，逐个存储]
20
21int next[4][2] = {
22 {0, 1}, //向右走
23 {1, 0}, //向下走
24 {0, -1}, //向左走
25 {-1, 0} //向上走
26};
27
28//首节点应传入-1
29int BFS(int u)
30{
31 //重置定位个数用的索引
32 int i = 0;
33 //判断是否是起点，若是只需要将起点存入即可，同时将轮数索引加 1
34 if (u == -1)
35 {
36 po[u + 1][0].x = begin_x;
37 po[u + 1][0].y = begin_y;
38 po[u + 1][0].is = 1;
39 //再次调用进行下一轮搜索
40 return BFS(u + 1);
41 }
42 //重置下一轮搜索的索引
43 int j = 0;
44 //判断父节点是否取尽
45 while (po[u][i].is == 1)
46 {
47 //搜索部分
48 int x = po[u][i].x;
49 int y = po[u][i].y;
50 //判断是否已经到达终点，若是则返回最短步数
51 if (x == end_x && y == end_y)
52 {
53 end_p = &po[u][i];
54 return u+1;
55 }
56 //将父节点设为不符合条件的节点，防止重复
57 map[x][y] = 1;
58
59 int k;
60 //循环搜索各方向
61 for (k = 0; k < 4; k++)
62 {
63 //定义临时x的坐标
64 int tx = x + next[k][0];
65 //定义临时y坐标
66 int ty = y + next[k][1];
67 //判断临时坐标是否到达边界，若是则尝试下一组
68 if (tx < 0 || tx >= n || ty < 0 || ty >= n)
69 {
70 continue;
71 }
72 //判断该节点的数据是否符合要求，若符合就将该节点存入队列
73 if (map[tx][ty] == 0)
74 {
75 //存入队列操作
76 po[u + 1][j].x = tx;
77 po[u + 1][j].y = ty;
78 //将存在数据的队列节点标记，方便遍历队列，省去传递队列个数的操作
79 po[u + 1][j].is = 1;
80 //定位上一个节点
81 po[u + 1][j].prev = &po[u][i];
82 //将子节点的索引递增一，防止下一个子节点覆盖上一个子节点
83 j++;
84 }
85 }
86 //将父节点的索引递增一，进行下一轮子节点的搜索
87 i++;
88 }
89 //当前父节点的所有子节点都已经搜索完毕，再次调用搜索函数，将当前所有子节点当成父节点，进行下一轮搜索
90 return BFS(u + 1);
91}
92
93int main(int argc, char const *argv[])
94{
95 //输入图
96 int i, j;
97 printf("输入要输入图的长宽\n");
98 scanf("%d", &n);
99 printf("输入数据\n");
100 for (i = 0; i < n; i++)
101 {
102 for (j = 0; j < n; j++)
103 {
104 scanf("%d", &map[j][i]);
105 }
106 }
107 // 定义存储输出轨迹的数组
108 int foot[100][2];
109 // 通过广度搜索返回最短步
110 int k=BFS(-1);
111 // 将每一步存入输出数组
112 for(i=0;i<k;i++)
113 {
114 foot[i][0] = end_p->y;
115 foot[i][1] = end_p->x;
116 // 重新定位指针
117 end_p = end_p->prev;
118 }
119 // 循环输出路径
120 for(i=k-1;i>0;i--)
121 {
122 printf("(%d, %d)->",foot[i][0],foot[i][1]);
123 }
124 printf("(%d, %d)\n",foot[i][0],foot[i][1]);
125 return 0;
126}本算法由于要进行寻迹操作，所以保留了每一层的数据，若不需要寻迹建议只保留两个队列，即两个一维结构体数组
2.DFS
深度优先搜索类似于广度优先搜索，也是一种图的搜索算法，但是不同于广度优先搜索，广搜注重范围，而深搜注重深度，通俗来说，广搜就是广撒网，深搜就是一路走到黑，不撞南墙不回头\(￣︶￣\))
算法的基本思路
深搜需要定义一个跟原图相同的数组，然后通过该数组对数据进行标记，若已经走过就标记，回到父节点时将父节点的标记取消，基础算法依旧使用递归
算法的实现
1#include <stdio.h>
2#include <limits.h>
3//深度优先搜索
4
5//地图数组
6int map[100][100];
7//标记数组，用于标记是否已经搜索过
8int book[100][100];
9//地图的个数，最短的步数
10int n, min = INT_MAX;
11//定义起点和终点
12int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;
13
14int next[4][2] = {
15 {0, 1}, //向右走
16 {1, 0}, //向下走
17 {0, -1}, //向左走
18 {-1, 0} //向上走
19};
20
21void DFS(int x, int y, int step)
22{
23 //判断是否已经到达终点，若是则比较目前的步数是否是最短的，若是则将当前步数赋给min，同时退出函数
24 if (x == end_x && y == end_y)
25 {
26 min = min < step ? min : step;
27 return;
28 }
29 int k;
30 if(x==0&&y==0) book[0][0] = 1;
31 //循环搜索各方向
32 for (k = 0; k < 4; k++)
33 {
34 //定义临时x的坐标
35 int tx = x + next[k][0];
36 //定义临时y坐标
37 int ty = y + next[k][1];
38 //判断临时坐标是否到达边界，若是则尝试下一组
39 if (tx < 0 || tx >= n || ty < 0 || ty >= n)
40 {
41 continue;
42 }
43 //判断该坐标的数据是否符合条件，若符合并且该数值之前没有被搜索到，就进行下一步搜索
44 if (map[tx][ty] == 0 && book[tx][ty] != 1)
45 {
46 //将该坐标标记为已经搜索过
47 book[tx][ty] = 1;
48 //进行下一步搜索，即向深层次搜索
49 DFS(tx, ty, step + 1);
50 //取消坐标标记，因为该坐标的子节点已经在上方的递归中搜索完毕
51 book[tx][ty] = 0;
52 }
53 }
54 return;
55}
56
57int main(int argc, char const *argv[])
58{
59 int i, j;
60 printf("输入要输入图的长宽\n");
61 scanf("%d", &n);
62 printf("输入数据\n");
63 for (i = 0; i < n; i++)
64 {
65 for (j = 0; j < n; j++)
66 {
67 scanf("%d", &map[j][i]);
68 }
69 }
70 end_x = n-1;
71 end_y = n-1;
72 DFS(begin_x, begin_y, 0);
73 //打印最短的步数
74 printf("%d", min);
75 return 0;
76}两种算法的比较
广搜由由于需要维护多条路径，同时存储多条路径，所以在正常情况下广搜使用的内存会比深搜多，编写也相对复杂，但是由于广搜一般是采用队列来存储路径所以没有爆栈的危险（C 语言不适用），而深搜是使用栈进行存储的，由于系统分配给程序的栈是有限的，所以当深度过高时深受可能会出现爆栈。
一般来说用 DFS 解决的问题都可以用 BFS 来解决。DFS 多用于连通性问题因为其运行思想与人脑的思维很相似，故解决连通性问题更自然。BFS 多用于解决最短路问题，其运行过程中需要储存每一层的信息，所以其运行时需要储存的信息量较大，资源的消耗也较多。但是在不同问题中两者占优的情况是不同的，当图较为复杂二者其实差别不大。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK