《算法八》（广度寻路算法）
广度寻路算法思路：
遍历整个地图中所有可以走的点
并且将其存入到一颗四叉树里
之后从起点开始搜索这棵树查找终点即可
1.各种类型定义：
//点类型
struct MyPoint{
int row;
int col;
};
//方向枚举
enum direct{p_up,p_down,p_left,p_right};
//辅助地图结点类型
struct pathNode{
int val;
bool isFind;
};
//树节点类型
struct treeNode{
MyPoint pos;
vector<treeNode*> child; //孩子 数组
treeNode* pParent;//父
};
//创建一个树节点并返回节点首地址
treeNode* CreateNode(int row, int col);
//创建一个树节点并返回节点首地址
treeNode* CreateNode(int row, int col){
treeNode* pNew = new treeNode;
memset(pNew, 0, sizeof(treeNode));
pNew->pos.row = row;
pNew->pos.col = col;
return pNew;
}
//判断pos点能不能走，能走返回true，不能返回false
bool canWalk(pathNode pathMap[ROWS][COLS], MyPoint pos);
//判断pos点能不能走，能走返回true，不能返回false
bool canWalk(pathNode pathMap[ROWS][COLS], MyPoint pos){
if (pathMap[pos.row][pos.col].isFind) //走过
return false;
if (pathMap[pos.row][pos.col].val) //障碍
return false;
return true;
}
2.主要寻路代码：
int main(){
//1 地图
int map[ROWS][COLS] = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 1, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
//2 辅助地图
pathNode pathMap[ROWS][COLS] = { 0 };
for (int i = 0; i < ROWS; i++){
for (int j = 0; j < COLS; j++)
pathMap[i][j].val = map[i][j];
}
//3 起点，终点
MyPoint begPos = { 1, 1 };
MyPoint endPos = { 8, 8 };
//4 准备树
treeNode* pRoot = NULL;
//5 起点为树的根节点
pRoot = CreateNode(begPos.row, begPos.col);
//6 标记起点已经走过
pathMap[begPos.row][begPos.col].isFind = true;
//7 寻路
//当前节点
MyPoint tempPos;
//当前层
vector<treeNode*> buff;
buff.push_back(pRoot);//树根为当前层
//临时树节点指针
treeNode* tempNode = NULL;
bool isFindEnd = false;//判断有没有找到终点
while (1){
#if 1
cout << "当前层：" << endl;
for (int i = 0; i < buff.size(); i++){
cout << "size:" << buff.size();
cout << "(" << buff[i]->pos.row << "," << buff[i]->pos.col << ") ";
}
#endif
//下一层
vector<treeNode*> nextBuff;
for (int i = 0; i < buff.size(); i++){//当前层每一个结点找孩子
for (int j = 0; j < 4; j++){//每一个结点都有四个方向
tempPos = buff[i]->pos;//当前层每一个结点
switch (j){
case p_up: tempPos.row--; break;//上 y--
case p_down: tempPos.row++; break;//下 y++
case p_left: tempPos.col--; break;//左 x--
case p_right: tempPos.col++; break;//右 x++
}
if (canWalk(pathMap,tempPos)){//如果能走
cout << "新节点:(" << tempPos.row << "," << tempPos.col << ")" << endl;
//标记新结点已经走过
pathMap[tempPos.row][tempPos.col].isFind = true;
//创建树节点
tempNode = CreateNode(tempPos.row, tempPos.col);
//新节点入树
buff[i]->child.push_back(tempNode); //当前点的孩子指针指向新结点
tempNode->pParent = buff[i]; //新节点的父指针指向当前点
//新节点保存到下一层数组中
nextBuff.push_back(tempNode);
//新结点是否是终点，是终点，跳出循环
if (tempPos.row == endPos.row &&
tempPos.col == endPos.col){
isFindEnd = true;
}
if (isFindEnd) break;
}
}
if (isFindEnd) break;
}
if (isFindEnd) break;
if (nextBuff.size() == 0)//找到最后也没有找到
break;
buff = nextBuff;//继续向下一层找
}
if (isFindEnd){
cout << "路径：" << endl;
while (tempNode){
cout << "(" << tempNode->pos.row << "," << tempNode->pos.col << ")" << endl;
tempNode = tempNode->pParent;
}
}
while (1);
return 0;
}
3.全部完整代码：
#include <iostream>
#include <vector>
#include<string.h>
using namespace std;
#define ROWS 10
#define COLS 10
//点类型
struct MyPoint{
int row;
int col;
};
//方向枚举
enum direct{p_up,p_down,p_left,p_right};
//辅助地图结点类型
struct pathNode{
int val;
bool isFind;
};
//树节点类型
struct treeNode{
MyPoint pos;
vector<treeNode*> child; //孩子 数组
treeNode* pParent;//父
};
//创建一个树节点并返回节点首地址
treeNode* CreateNode(int row, int col);
//创建一个树节点并返回节点首地址
treeNode* CreateNode(int row, int col){
treeNode* pNew = new treeNode;
memset(pNew, 0, sizeof(treeNode));
pNew->pos.row = row;
pNew->pos.col = col;
return pNew;
}
//判断pos点能不能走，能走返回true，不能返回false
bool canWalk(pathNode pathMap[ROWS][COLS], MyPoint pos);
//判断pos点能不能走，能走返回true，不能返回false
bool canWalk(pathNode pathMap[ROWS][COLS], MyPoint pos){
if (pathMap[pos.row][pos.col].isFind) //已经走过
return false;
if (pathMap[pos.row][pos.col].val) //有障碍物
return false;
return true;
}
int main(){
//1 地图
int map[ROWS][COLS] = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 1, 0, 1, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 1, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
//2 辅助地图
pathNode pathMap[ROWS][COLS] = { 0 };
for (int i = 0; i < ROWS; i++){
for (int j = 0; j < COLS; j++)
pathMap[i][j].val = map[i][j];
}
//3 起点，终点
MyPoint begPos = { 1, 1 };
MyPoint endPos = { 8, 8 };
//4 准备树
treeNode* pRoot = NULL;
//5 起点为树的根节点
pRoot = CreateNode(begPos.row, begPos.col);
//6 标记起点已经走过
pathMap[begPos.row][begPos.col].isFind = true;
//7 寻路
//当前节点
MyPoint tempPos;
//当前层
vector<treeNode*> buff;
buff.push_back(pRoot);//树根为当前层
//临时树节点指针
treeNode* tempNode = NULL;
bool isFindEnd = false;//判断有没有找到终点
while (1){
#if 1
cout << "当前层：" << endl;
for (int i = 0; i < buff.size(); i++){
cout << "size:" << buff.size();
cout << "(" << buff[i]->pos.row << "," << buff[i]->pos.col << ") ";
}
#endif
//下一层
vector<treeNode*> nextBuff;
for (int i = 0; i < buff.size(); i++){//当前层每一个结点找孩子
for (int j = 0; j < 4; j++){//每一个结点都有四个方向
tempPos = buff[i]->pos;//当前层每一个结点
switch (j){
case p_up: tempPos.row--; break;//上 y--
case p_down: tempPos.row++; break;//下 y++
case p_left: tempPos.col--; break;//左 x--
case p_right: tempPos.col++; break;//右 x++
}
if (canWalk(pathMap,tempPos)){//如果能走
cout << "新节点:(" << tempPos.row << "," << tempPos.col << ")" << endl;
//标记新结点已经走过
pathMap[tempPos.row][tempPos.col].isFind = true;
//创建树节点
tempNode = CreateNode(tempPos.row, tempPos.col);
//新节点入树
buff[i]->child.push_back(tempNode); //当前点的孩子指针指向新结点
tempNode->pParent = buff[i]; //新节点的父指针指向当前点
//新节点保存到下一层数组中
nextBuff.push_back(tempNode);
//新结点是否是终点，是终点，跳出循环
if (tempPos.row == endPos.row &&
tempPos.col == endPos.col){
isFindEnd = true;
}
if (isFindEnd) break;
}
}
if (isFindEnd) break;
}
if (isFindEnd) break;
if (nextBuff.size() == 0)//找到最后也没有找到
break;
buff = nextBuff;//继续向下一层找
}
if (isFindEnd){
cout << "路径：" << endl;
while (tempNode){
cout << "(" << tempNode->pos.row << "," << tempNode->pos.col << ")" << endl;
tempNode = tempNode->pParent;
}
}
while (1);
return 0;
}
//创建一个树节点并返回节点首地址
treeNode* CreateNode(int row, int col){
treeNode* pNew = new treeNode;
memset(pNew, 0, sizeof(treeNode));
pNew->pos.row = row;
pNew->pos.col = col;
return pNew;
}
//判断pos点能不能走，能走返回true，不能返回false
bool canWalk(pathNode pathMap[ROWS][COLS], MyPoint pos){
if (pathMap[pos.row][pos.col].isFind) //走过
return false;
if (pathMap[pos.row][pos.col].val) //障碍
return false;
return true;
}
/*
深度寻路：
有回退 循环少 适用于宽阔大地图 不一定能找到最短路径
广度寻路：
没有回退 循环多 适用与小地图 一定能找到最短路径
都只能走直线
*/
4.小总结：
深度寻路：
有回退 循环少 适用于宽阔大地图 不一定能找到最短路径
广度寻路：
没有回退 循环多 适用与小地图 一定能找到最短路径
但是都只能走直线
版权声明：本文为Whgy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。