【C++】广度/深度优先算法（bfs+dfs）理解+例题+对比
2018-08-04 本文已影响0人
Buyun0
例题：
《迷宫问题》
定义一个二维数组：
0 0 1 0 1 //0表示可走，1表示墙
0 1 1 1 0 //只能↑↓←→走，不能斜着走
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0 //题目保证了输入是一定有解的
求从左上角（0，0）到右下角（4，4）的最短路线。
bfs解题核心逻辑伪代码：
1，将起点推入队列中；
2，将起点标识为已走过；
while（队列非空）{
3，取队列首节点vt，并从队列中弹出；
4，探索上面取出得节点的周围是否有没走过的节点vf，如果有将所有能走的vf的parents指向vt，并将vf加入队列
（如果vf等于终点，说明探索完成，退出循环）。
}
如果队列为空自然跳出，说明无路可达终点。
实际c++实现：
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
struct Node//定义结构体Node
{
int xx ;//自身处于组内的位置
int yy;
bool qiang;//是否是墙
bool walked;//是否走过
Node *parents;//指向父节点的指针
};
int main() {
int id = 0;
//int xx, yy;
queue<Node*> bfs;//创建Node指针队列
vector<vector<Node>> migong;//创建二维迷宫组
for (int i = 0; i < 5; i++) {
vector<Node> hang;
for (int j = 0; j < 5; j++) {
int ii;
cin >> ii;
Node node{ i,j,ii,false};
hang.push_back(node);
}
migong.push_back(hang);
}
//输入完毕
int ax[4] = { -1,1,0,0 };
int by[4] = { 0,0,1,-1 };
bfs.push(&migong[0][0]);//先将起点推进去
migong[0][0].walked = true;
Node *vt;//等下指向父节点的指针
Node *vf;//等下指向父节点引申出的子节点
while (!bfs.empty()) {
vt = bfs.front();
bfs.pop();
if ((*vt).xx >= 1) {//查询左节点是否可以
vf = &migong[(*vt).xx + ax[0]][(*vt).yy + by[0]];
if (!(*vf).qiang && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;//子节点指向父节点
if ((*vf).xx == 4 && (*vf).yy == 4) break;//如果是终点节点，结束寻找，跳出循环。
}
}
if ((*vt).xx <=3 ) {//查询右节点是否可以
vf = &migong[(*vt).xx + ax[1]][(*vt).yy + by[1]];
if (!(*vf).qiang && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;
if ((*vf).xx == 4 && (*vf).yy == 4) break;
}
}
if ((*vt).yy <= 3) {//查询下节点是否可以
vf = &migong[(*vt).xx + ax[2]][(*vt).yy + by[2]];
if (!(*vf).qiang && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;
if ((*vf).xx == 4 && (*vf).yy == 4) break;
}
}
if ((*vt).yy >= 1) {//查询上节点是否可以
vf = &migong[(*vt).xx + ax[3]][(*vt).yy + by[3]];
if (!(*vf).qiang && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;
if ((*vf).xx == 4 && (*vf).yy == 4) break;
}
}
}
//结束算法，从vf指向的节点开始寻找父节点。
vector<Node*> fin;
while (true) {
fin.push_back(vf);
vf = (*vf).parents;
if ((*vf).xx == 0 && (*vf).yy == 0) {
fin.push_back(vf);
break;
}
}
//输出
for (int i = fin.size()-1; i >=0;i--) {
cout << (*fin[i]).xx << "," << (*fin[i]).yy << endl;
}
return 0;
}
输出示例：
0 0 1 0 1
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
0,0
1,0
2,0
2,1
2,2
2,3
2,4
3,4
4,4
dfs解题核心逻辑伪代码：
1，栈初始化
2，获得起点，将起点标识为已走过，将起点入栈
while（栈非空）{
取栈顶元素vt
如果vt周围有为走过的节点vf，则：
将vf改为已走
vf入栈
没有能走的节点，vt出栈
}
代码：
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<queue>
#include<string>
#include<stack>
#include<time.h>
#include <windows.h>
#include<set>
using namespace std;
struct Node
{
int x;
int y;
bool walked;
int g;
int f;//f = g+h
int h;
Node* parents;
};
int main() {
vector<vector<Node>> migong;//创建二维迷宫组
for (int i = 0; i < 5; i++) {
vector<Node> hang;
for (int j = 0; j < 5; j++) {
int ii;
cin >> ii;
Node node{ i,j,ii };
hang.push_back(node);
}
migong.push_back(hang);
}
/*-----------------------------------dfs----------------------------------------------*/
vector<vector<Node>> migong2 = migong;
stack<Node*> f;
f.push(&migong2[0][0]);
migong2[0][0].walked = true;
while (!f.empty()) {
Node *vt = f.top();
bool can = true;
if (vt->x >= 1) {
Node *vf = &migong2[vt->x - 1][vt->y];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (vt->x <=3) {
Node *vf = &migong2[vt->x + 1][vt->y];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (vt->y >= 1) {
Node *vf = &migong2[vt->x][vt->y - 1];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (vt->y <= 3) {
Node *vf = &migong2[vt->x ][vt->y + 1];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (can) {
f.pop();
}
}
vector<Node*> fin2;
Node*bb = &migong2[4][4];
while (true) {
fin2.push_back(aa);
if (bb == &migong2[0][0]) {
break;
}
bb = bb->parents;
}
int count2 = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << migong2[i][j].walked;
if (migong2[i][j].walked)count2++;
}
cout << endl;
}
reverse(fin2.begin(), fin2.end());
for (int i = 0; i < fin.size(); i++) {
cout << fin[i]->x <<" "<< fin[i]->y<< endl;
}
return 0;
}
输出：
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
11000
11111
11111
11111
00011
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
两种方法的时间对比以及路径分析：
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<queue>
#include<string>
#include<stack>
#include<time.h>
#include <windows.h>
#include<set>
using namespace std;
struct Node
{
int x;
int y;
bool walked;
int g;
int f;//f = g+h
int h;
Node* parents;
};
int main() {
int qiang = 0;
vector<vector<Node>> migong;//创建二维迷宫组
for (int i = 0; i < 5; i++) {
vector<Node> hang;
for (int j = 0; j < 5; j++) {
int ii;
cin >> ii;
if (ii) qiang++;
Node node{ i,j,ii };
hang.push_back(node);
}
migong.push_back(hang);
}
int a[10002];
int i = 0;
double run_time;
_LARGE_INTEGER time_start; //开始时间
_LARGE_INTEGER time_over; //结束时间
double dqFreq; //计时器频率
LARGE_INTEGER ff; //计时器频率
QueryPerformanceFrequency(&ff);
dqFreq = (double)ff.QuadPart;
QueryPerformanceCounter(&time_start);
/*-----------------------------------dfs----------------------------------------------*/
vector<vector<Node>> migong2 = migong;
stack<Node*> f;
f.push(&migong2[0][0]);
migong2[0][0].walked = true;
while (!f.empty()) {
Node *vt = f.top();
bool can = true;
if (vt->x >= 1) {
Node *vf = &migong2[vt->x - 1][vt->y];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (vt->x <=3) {
Node *vf = &migong2[vt->x + 1][vt->y];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (vt->y >= 1) {
Node *vf = &migong2[vt->x][vt->y - 1];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (vt->y <= 3) {
Node *vf = &migong2[vt->x ][vt->y + 1];
if (vf->walked == false) {
vf->parents = vt;
vf->walked = true;
if (vf == &migong2[4][4]) {
break;
}
f.push(vf);
can = false;
}
}
if (can) {
f.pop();
}
}
QueryPerformanceCounter(&time_over); //计时结束
run_time = 1000000 * (time_over.QuadPart - time_start.QuadPart) / dqFreq;
float time1 = run_time;
QueryPerformanceFrequency(&ff);
dqFreq = (double)ff.QuadPart;
QueryPerformanceCounter(&time_start);
/*-----------------------------------bfs----------------------------------------------*/
int ax[4] = { -1,1,0,0 };
int by[4] = { 0,0,1,-1 };
queue<Node*> bfs;
bfs.push(&migong[0][0]);//先将起点推进去
migong[0][0].walked = true;
Node *vt;//等下指向父节点的指针
Node *vf;//等下指向父节点引申出的子节点
while (!bfs.empty()) {
vt = bfs.front();
bfs.pop();
if ((*vt).x >= 1) {//查询左节点是否可以
vf = &migong[(*vt).x + ax[0]][(*vt).y + by[0]];
if (!(*vf).walked && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;//子节点指向父节点
if ((*vf).x == 4 && (*vf).y == 4) break;//如果是终点节点，结束寻找，跳出循环。
}
}
if ((*vt).x <= 3) {//查询右节点是否可以
vf = &migong[(*vt).x + ax[1]][(*vt).y + by[1]];
if (!(*vf).walked && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;
if ((*vf).x == 4 && (*vf).y == 4) break;
}
}
if ((*vt).y <= 3) {//查询下节点是否可以
vf = &migong[(*vt).x + ax[2]][(*vt).y + by[2]];
if (!(*vf).walked && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;
if ((*vf).x == 4 && (*vf).y == 4) break;
}
}
if ((*vt).y >= 1) {//查询上节点是否可以
vf = &migong[(*vt).x + ax[3]][(*vt).y + by[3]];
if (!(*vf).walked && !(*vf).walked) {
bfs.push(vf);
(*vf).walked = true;
(*vf).parents = vt;
if ((*vf).x == 4 && (*vf).y == 4) break;
}
}
}
QueryPerformanceCounter(&time_over); //计时结束
run_time = 1000000 * (time_over.QuadPart - time_start.QuadPart) / dqFreq;
float time2 = run_time;
/*-----------------------------------A*----------------------------------------------*/
vector<vector<Node>> migong3 = migong;
set<Node*> openNode;
set<Node*> closeNode;
openNode.insert(&migong3[0][0]);
/*-----------------------------------结束----------------------------------------------*/
vector<Node*> fin;
Node*aa = &migong[4][4];
while (true) {
fin.push_back(aa);
if (aa == &migong[0][0]) {
break;
}
aa = aa->parents;
}
vector<Node*> fin2;
Node*bb = &migong2[4][4];
while (true) {
fin2.push_back(bb);
if (bb == &migong2[0][0]) {
break;
}
bb = bb->parents;
}
cout << "bfs运行后矩阵" << endl;
int count = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << migong[i][j].walked;
if (migong[i][j].walked)count++;
}
cout << endl;
}
reverse(fin.begin(), fin.end());
cout << "dfs运行后矩阵" << endl;
int count2 = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << migong2[i][j].walked;
if (migong2[i][j].walked)count2++;
}
cout << endl;
}
reverse(fin2.begin(), fin2.end());
for (int i = 0; i < fin.size(); i++) {
cout << fin[i]->x <<" "<< fin[i]->y<< endl;
}
cout << "Totle Time of dfs : " << time1 << "s" << endl;
cout << "Totle Time of bfs: " << time2 << "s" << endl;
cout << "bfs共搜索过的节点数：" << count- qiang << endl;
cout << "dfs共搜索过的节点数：" << count2- qiang << endl;
return 0;
//https://blog.csdn.net/u012878643/article/details/46723375
}
输出示例1：
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
bfs运行后矩阵
11001
11111
11111
11111
11111
dfs运行后矩阵
11000
11111
11111
11111
00011
bfs路径
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
dfs路径
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
Totle Time of dfs : 65.5013s
Totle Time of bfs: 67.3427s
bfs共搜索过的节点数：15
dfs共搜索过的节点数：11
输出示例2：
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
bfs运行后矩阵
11111
11111
11111
11111
11111
dfs运行后矩阵
11111
11111
11111
11111
11111
bfs路径
0 0
1 0
2 0
3 0
4 0
4 1
4 2
4 3
4 4
dfs路径
0 0
0 1
0 2
0 3
0 4
1 4
2 4
2 3
2 2
2 1
2 0
3 0
4 0
4 1
4 2
4 3
4 4
Totle Time of dfs : 133.107s
Totle Time of bfs: 131.792s
bfs共搜索过的节点数：25
dfs共搜索过的节点数：25
输出示例3：
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
bfs运行后矩阵
11111
11111
11111
11111
11111
dfs运行后矩阵
11111
11111
11111
11111
11111
bfs路径
0 0
1 0
2 0
3 0
4 0
4 1
4 2
4 3
4 4
dfs路径
0 0
0 1
0 2
0 3
0 4
1 4
2 4
2 3
2 2
2 1
2 0
3 0
4 0
4 1
4 2
4 3
4 4
Totle Time of dfs : 120.217s
Totle Time of bfs: 99.1726s
bfs共搜索过的节点数：19
dfs共搜索过的节点数：19
参考：dfs详解
