BFS，即 Breath First Search（广度优先搜索）
DFS，即 Deep First Search （深度优先搜索）
图的搜索是对于连通图的一种遍历策略，常用于走迷宫的问题
本文的算法基于 C 语言编写，过几天会使用 Java 重写这两个算法
另外本文的算法是对基于数组的图进行搜索，基于链表的搜索暂时未弄 （逃
1.BFS
广度优先搜索顾名思义，就是在广范围进行搜索，从一个顶点 V0 开始，辐射状地优先遍历其周围较广的区域
算法的基本思路
在广搜中不需要记录节点是否走过，但是要记录上一个节点的位置，若将整个过程画成树，即可观察到广搜是一层一层进行遍历的（这里就不画图了，逃），这时若要搜索下一层节点就需要读取上一层节点的位置，并对父节点的所有节点逐个进行搜索，将符合要求的子节点逐个存入下一层节点，直到判断到达终点即停止搜索
基础算法采用递归，存储搜索各层节点采用队列，但由于 C 语言中没有队列所以采用结构体数组代替，使用二维结构体数组，其中一维对应层数，另一维存储该层的节点，另外若要使广搜拥有寻迹功能，即可以输出行进路程中每一步，就需要在结构体中增加一个结构体指针指向父节点，然后记录最后一个节点的地址，通过访问指针来访问父节点，直到到达起点
算法的实现
#include <stdio.h>
//广度优先搜索 - 可寻迹
//地图数组
int map[100][100];
//地图的个数
int n;
//定义起点和终点
int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;
//能到达终点的最后一个节点的指针
struct POINT *end_p = NULL;
//步进存储结构体
struct POINT
{
int x; //X轴坐标
int y; //Y轴坐标
int is = 0; //是否是达到需求的节点，作为下一轮搜索的索引
struct POINT *prev;
} po[100][100]; //po[轮数][不同节点存储，逐个存储]
int next[4][2] = {
{0, 1}, //向右走
{1, 0}, //向下走
{0, -1}, //向左走
{-1, 0} //向上走
};
//首节点应传入-1
int BFS(int u)
{
//重置定位个数用的索引
int i = 0;
//判断是否是起点，若是只需要将起点存入即可，同时将轮数索引加 1
if (u == -1)
{
po[u + 1][0].x = begin_x;
po[u + 1][0].y = begin_y;
po[u + 1][0].is = 1;
//再次调用进行下一轮搜索
return BFS(u + 1);
}
//重置下一轮搜索的索引
int j = 0;
//判断父节点是否取尽
while (po[u][i].is == 1)
{
//搜索部分
int x = po[u][i].x;
int y = po[u][i].y;
//判断是否已经到达终点，若是则返回最短步数
if (x == end_x && y == end_y)
{
end_p = &po[u][i];
return u+1;
}
//将父节点设为不符合条件的节点，防止重复
map[x][y] = 1;
int k;
//循环搜索各方向
for (k = 0; k < 4; k++)
{
//定义临时x的坐标
int tx = x + next[k][0];
//定义临时y坐标
int ty = y + next[k][1];
//判断临时坐标是否到达边界，若是则尝试下一组
if (tx < 0 || tx >= n || ty < 0 || ty >= n)
{
continue;
}
//判断该节点的数据是否符合要求，若符合就将该节点存入队列
if (map[tx][ty] == 0)
{
//存入队列操作
po[u + 1][j].x = tx;
po[u + 1][j].y = ty;
//将存在数据的队列节点标记，方便遍历队列，省去传递队列个数的操作
po[u + 1][j].is = 1;
//定位上一个节点
po[u + 1][j].prev = &po[u][i];
//将子节点的索引递增一，防止下一个子节点覆盖上一个子节点
j++;
}
}
//将父节点的索引递增一，进行下一轮子节点的搜索
i++;
}
//当前父节点的所有子节点都已经搜索完毕，再次调用搜索函数，将当前所有子节点当成父节点，进行下一轮搜索
return BFS(u + 1);
}
int main(int argc, char const *argv[])
{
//输入图
int i, j;
printf("输入要输入图的长宽\n");
scanf("%d", &n);
printf("输入数据\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &map[j][i]);
}
}
// 定义存储输出轨迹的数组
int foot[100][2];
// 通过广度搜索返回最短步
int k=BFS(-1);
// 将每一步存入输出数组
for(i=0;i<k;i++)
{
foot[i][0] = end_p->y;
foot[i][1] = end_p->x;
// 重新定位指针
end_p = end_p->prev;
}
// 循环输出路径
for(i=k-1;i>0;i--)
{
printf("(%d, %d)->",foot[i][0],foot[i][1]);
}
printf("(%d, %d)\n",foot[i][0],foot[i][1]);
return 0;
}#include <stdio.h>
//广度优先搜索 - 可寻迹
//地图数组
int map[100][100];
//地图的个数
int n;
//定义起点和终点
int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;
//能到达终点的最后一个节点的指针
struct POINT *end_p = NULL;
//步进存储结构体
struct POINT
{
int x; //X轴坐标
int y; //Y轴坐标
int is = 0; //是否是达到需求的节点，作为下一轮搜索的索引
struct POINT *prev;
} po[100][100]; //po[轮数][不同节点存储，逐个存储]
int next[4][2] = {
{0, 1}, //向右走
{1, 0}, //向下走
{0, -1}, //向左走
{-1, 0} //向上走
};
//首节点应传入-1
int BFS(int u)
{
//重置定位个数用的索引
int i = 0;
//判断是否是起点，若是只需要将起点存入即可，同时将轮数索引加 1
if (u == -1)
{
po[u + 1][0].x = begin_x;
po[u + 1][0].y = begin_y;
po[u + 1][0].is = 1;
//再次调用进行下一轮搜索
return BFS(u + 1);
}
//重置下一轮搜索的索引
int j = 0;
//判断父节点是否取尽
while (po[u][i].is == 1)
{
//搜索部分
int x = po[u][i].x;
int y = po[u][i].y;
//判断是否已经到达终点，若是则返回最短步数
if (x == end_x && y == end_y)
{
end_p = &po[u][i];
return u+1;
}
//将父节点设为不符合条件的节点，防止重复
map[x][y] = 1;
int k;
//循环搜索各方向
for (k = 0; k < 4; k++)
{
//定义临时x的坐标
int tx = x + next[k][0];
//定义临时y坐标
int ty = y + next[k][1];
//判断临时坐标是否到达边界，若是则尝试下一组
if (tx < 0 || tx >= n || ty < 0 || ty >= n)
{
continue;
}
//判断该节点的数据是否符合要求，若符合就将该节点存入队列
if (map[tx][ty] == 0)
{
//存入队列操作
po[u + 1][j].x = tx;
po[u + 1][j].y = ty;
//将存在数据的队列节点标记，方便遍历队列，省去传递队列个数的操作
po[u + 1][j].is = 1;
//定位上一个节点
po[u + 1][j].prev = &po[u][i];
//将子节点的索引递增一，防止下一个子节点覆盖上一个子节点
j++;
}
}
//将父节点的索引递增一，进行下一轮子节点的搜索
i++;
}
//当前父节点的所有子节点都已经搜索完毕，再次调用搜索函数，将当前所有子节点当成父节点，进行下一轮搜索
return BFS(u + 1);
}
int main(int argc, char const *argv[])
{
//输入图
int i, j;
printf("输入要输入图的长宽\n");
scanf("%d", &n);
printf("输入数据\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &map[j][i]);
}
}
// 定义存储输出轨迹的数组
int foot[100][2];
// 通过广度搜索返回最短步
int k=BFS(-1);
// 将每一步存入输出数组
for(i=0;i<k;i++)
{
foot[i][0] = end_p->y;
foot[i][1] = end_p->x;
// 重新定位指针
end_p = end_p->prev;
}
// 循环输出路径
for(i=k-1;i>0;i--)
{
printf("(%d, %d)->",foot[i][0],foot[i][1]);
}
printf("(%d, %d)\n",foot[i][0],foot[i][1]);
return 0;
}本算法由于要进行寻迹操作，所以保留了每一层的数据，若不需要寻迹建议只保留两个队列，即两个一维结构体数组
2.DFS
深度优先搜索类似于广度优先搜索，也是一种图的搜索算法，但是不同于广度优先搜索，广搜注重范围，而深搜注重深度，通俗来说，广搜就是广撒网，深搜就是一路走到黑，不撞南墙不回头\(￣︶￣\))
算法的基本思路
深搜需要定义一个跟原图相同的数组，然后通过该数组对数据进行标记，若已经走过就标记，回到父节点时将父节点的标记取消，基础算法依旧使用递归
算法的实现
#include <stdio.h>
#include <limits.h>
//深度优先搜索
//地图数组
int map[100][100];
//标记数组，用于标记是否已经搜索过
int book[100][100];
//地图的个数，最短的步数
int n, min = INT_MAX;
//定义起点和终点
int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;
int next[4][2] = {
{0, 1}, //向右走
{1, 0}, //向下走
{0, -1}, //向左走
{-1, 0} //向上走
};
void DFS(int x, int y, int step)
{
//判断是否已经到达终点，若是则比较目前的步数是否是最短的，若是则将当前步数赋给min，同时退出函数
if (x == end_x && y == end_y)
{
min = min < step ? min : step;
return;
}
int k;
if(x==0&&y==0) book[0][0] = 1;
//循环搜索各方向
for (k = 0; k < 4; k++)
{
//定义临时x的坐标
int tx = x + next[k][0];
//定义临时y坐标
int ty = y + next[k][1];
//判断临时坐标是否到达边界，若是则尝试下一组
if (tx < 0 || tx >= n || ty < 0 || ty >= n)
{
continue;
}
//判断该坐标的数据是否符合条件，若符合并且该数值之前没有被搜索到，就进行下一步搜索
if (map[tx][ty] == 0 && book[tx][ty] != 1)
{
//将该坐标标记为已经搜索过
book[tx][ty] = 1;
//进行下一步搜索，即向深层次搜索
DFS(tx, ty, step + 1);
//取消坐标标记，因为该坐标的子节点已经在上方的递归中搜索完毕
book[tx][ty] = 0;
}
}
return;
}
int main(int argc, char const *argv[])
{
int i, j;
printf("输入要输入图的长宽\n");
scanf("%d", &n);
printf("输入数据\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &map[j][i]);
}
}
end_x = n-1;
end_y = n-1;
DFS(begin_x, begin_y, 0);
//打印最短的步数
printf("%d", min);
return 0;
}#include <stdio.h>
#include <limits.h>
//深度优先搜索
//地图数组
int map[100][100];
//标记数组，用于标记是否已经搜索过
int book[100][100];
//地图的个数，最短的步数
int n, min = INT_MAX;
//定义起点和终点
int begin_x = 0, begin_y = 0, end_x = 4, end_y = 4;
int next[4][2] = {
{0, 1}, //向右走
{1, 0}, //向下走
{0, -1}, //向左走
{-1, 0} //向上走
};
void DFS(int x, int y, int step)
{
//判断是否已经到达终点，若是则比较目前的步数是否是最短的，若是则将当前步数赋给min，同时退出函数
if (x == end_x && y == end_y)
{
min = min < step ? min : step;
return;
}
int k;
if(x==0&&y==0) book[0][0] = 1;
//循环搜索各方向
for (k = 0; k < 4; k++)
{
//定义临时x的坐标
int tx = x + next[k][0];
//定义临时y坐标
int ty = y + next[k][1];
//判断临时坐标是否到达边界，若是则尝试下一组
if (tx < 0 || tx >= n || ty < 0 || ty >= n)
{
continue;
}
//判断该坐标的数据是否符合条件，若符合并且该数值之前没有被搜索到，就进行下一步搜索
if (map[tx][ty] == 0 && book[tx][ty] != 1)
{
//将该坐标标记为已经搜索过
book[tx][ty] = 1;
//进行下一步搜索，即向深层次搜索
DFS(tx, ty, step + 1);
//取消坐标标记，因为该坐标的子节点已经在上方的递归中搜索完毕
book[tx][ty] = 0;
}
}
return;
}
int main(int argc, char const *argv[])
{
int i, j;
printf("输入要输入图的长宽\n");
scanf("%d", &n);
printf("输入数据\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
scanf("%d", &map[j][i]);
}
}
end_x = n-1;
end_y = n-1;
DFS(begin_x, begin_y, 0);
//打印最短的步数
printf("%d", min);
return 0;
}两种算法的比较
广搜由由于需要维护多条路径，同时存储多条路径，所以在正常情况下广搜使用的内存会比深搜多，编写也相对复杂，但是由于广搜一般是采用队列来存储路径所以没有爆栈的危险（C 语言不适用），而深搜是使用栈进行存储的，由于系统分配给程序的栈是有限的，所以当深度过高时深受可能会出现爆栈。
一般来说用 DFS 解决的问题都可以用 BFS 来解决。DFS 多用于连通性问题因为其运行思想与人脑的思维很相似，故解决连通性问题更自然。BFS 多用于解决最短路问题，其运行过程中需要储存每一层的信息，所以其运行时需要储存的信息量较大，资源的消耗也较多。但是在不同问题中两者占优的情况是不同的，当图较为复杂二者其实差别不大。
图的搜索(遍历) - BFS & DFS
https://blog.ixk.me/post/graph-search-bfs-dfs许可协议
BY-NC-SA
本文作者
Otstar Lin
发布于
2018/12/19
转载或引用本文时请遵守许可协议，注明出处、不得用于商业用途！