图搜索算法---广度优先搜索
广度优先：bfs
一、注意事项
1.走直线，不能走斜线
2.理解为树的层次次序
3.如果有路，必然找到最短路径
4.需要遍历所有可通行的节点，如果地图比较大，开销就比较大
5.如果已经搜索过，就不再搜索
6.同时向所有可通过的的方向进行搜索
思路：其实和深度优先搜索没什么区别，就是在判断的时候，深度始终是一个点一个点的走，而广度会把下一步能走的路都走一遍
资源数组不要改动
二、代码示例
#include<iostream>
using namespace std;
#define MAP_ROW 6
#define MAP_COL 8
//路径点信息
struct MyPoint
{
int row, col;
};
//寻路的方向
enum PathDir
{
p_up, p_down, p_left, p_right
};
//辅助数组中元素的类型（结构体）
struct PathNode
{
int val;//原始数组的原始地图的值
PathDir dir;//保存这个路径寻路的方向，为数组中每一个元素准备一个方向
bool isFind;//标记这个路径点是否走过
};
//准备树形结构的节点类型
#include<vector>
struct MyTreeNode
{
MyPoint pos;//数据域，记录着某个行列坐标，表示一个路径点
MyTreeNode* parent;//当前节点的父节点
vector<MyTreeNode*> child;//指向当前节点所有子节点的指针数组
};
//清除树形结构中的所有节点
void clearTree(MyTreeNode*&root)
{
if (root)
{
for (size_t i = 0; i < root->child.size(); i++)
{
clearTree(root->child[i]);
}
delete root;
root = nullptr;
}
}
bool checkPoint(PathNode arr[][MAP_COL], MyPoint p)
{
if (p.row >= 0 && p.col >= 0 && p.row < MAP_ROW&&p.col < MAP_COL)
{
//表示在地图范围之内
//表示要可通行并且路径点没有被访问
if (arr[p.row][p.col].val == 0 && !arr[p.row][p.col].isFind)
{
return true;
}
}
return false;
}
int main()
{
//原始地图
int arr[MAP_ROW][MAP_COL] = {
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 }
};
//因为原来的地图不能改动，所以要准备一个辅助数组，用来存储原数组的数据，而且还将辅助地图中的元素，加了几个属性，一个是数组中元素的寻路方向，还有标记了当前路径点是否被访问
//准备辅助地图
PathNode pathArr[MAP_ROW][MAP_COL];
for (int i = 0; i < MAP_ROW; i++)
{
for (int j = 0; j < MAP_COL; j++)
{
pathArr[i][j].val = arr[i][j];//将原地图的坐标保存到辅助地图中
pathArr[i][j].dir = p_up;//记录寻路方向
pathArr[i][j].isFind = false;//表示还未走过
}
}
//准备起点和终点
MyPoint beginPoint = { 2,3 };
MyPoint endPoint = { 4,6 };
pathArr[beginPoint.row][beginPoint.col].isFind = true;//将起点标记为已访问
//开始搜索，并保存搜索的数据
MyTreeNode* pRoot = new MyTreeNode;//分配一个内存给根节点
pRoot->pos = beginPoint;//根节点里面的路径点就是起点
pRoot->parent = nullptr;//根节点是没有父节点的
//根节点到目前为止，子节点是未知的，并不知道child是怎样赋值的
//因为树形结构表兄弟之间无法直接联系，需要借助两个辅助数组来保存节点的首地址
//两个辅助数组，一个用来表示父节点层的所有元素的首地址，一个是用来表示子节点层的所有元素的首地址
//指针数组，每一个元素都是指针
vector<MyTreeNode*> currentList;//表示当前节点层（子节点层）
vector<MyTreeNode*> nextList;//表示当前节点层的下一层（子节点层）
currentList.push_back(pRoot);//表示当前父节点层为根节点，通过这个去搜索根节点的子节点层
MyPoint tempPoint;//临时变量，用来记录当前位置的下一个位置的行列
//开始搜索--逻辑代码
while (true)//不知道怎么退出，就写成死循环
{
//循环查找父节点层的所有元素，次数表示当前父节点层有多少个元素
for (int i = 0; i < (int)currentList.size(); i++)
{
//四个方向循环查找
for (int j = 0; j < 4; j++)
{
//在这里初始化的目的是要循环四个方向，让临时变量==父节点层中每一个元素的坐标位置
tempPoint = currentList[i]->pos;
switch (j)
{
case p_up:
tempPoint.row--;
break;
case p_down:
tempPoint.row++;
break;
case p_left:
tempPoint.col++;
break;
case p_right:
tempPoint.col--;
break;
}
if (checkPoint(pathArr, tempPoint))
{
//表示可通行
//准备构建树形结构
MyTreeNode* insertNode = new MyTreeNode;//待插入节点申请内存
//指向临时变量
insertNode->pos = tempPoint;
//树形结构的建立
//子节点关联上父节点
insertNode->parent = currentList[i];//currentList[i]是一个指针，指向一个路径点
//父节点关联上子节点
currentList[i]->child.push_back(insertNode);
//标记当前节点已访问
pathArr[tempPoint.row][tempPoint.col].isFind = true;
//将当前节点压入子节点层中
nextList.push_back(insertNode);
if (insertNode->pos.row == endPoint.row&&insertNode->pos.col == endPoint.col)
{
//表示找到了终点
MyTreeNode* pNode = insertNode;
while (pNode)
{
printf("row=%d, col=%d
", pNode->pos.row, pNode->pos.col);
pNode = pNode->parent;
}
goto LABED;
}
}
}
}
//表示没有找到终点
if (nextList.size() == 0)
{
goto LABED;
}
currentList = nextList;//将原来的子节点变为父节点层，在把原来的子节点层中所有的数据删除
nextList.clear();
}
LABED:
clearTree(pRoot);//清除树中数据
return 0;
}