深度优先搜索(depth first search(dfs)) 和 广度/宽度优先搜索(breath first search(bfs))

（一）深度优先搜索(depth first search(dfs)):

沿着一个方向一直找,直到走不了,回到上一个分支,继续;

dfs:解析

1.将起始点放入path中,并且标记为走过
2.dfs:
	 步骤：
1.起点存入路径中：  先上下左右
2.递归流程（x.y)
	1:判断x,y是否是终点，如果是终点，递归结束
	2.遍历x,y周围四个点 xx,yy
	{
		1.判断xx.yy组成的点是否能走，（不是障碍物，没有走过，没有越界）
		2..如果能走，递归XX.YY.组成的点（dfs(xx,yy))
		3.递归结束后没有找到路径，将xx,yy组成的点移除出路径
	}
3.如果全部递归结束，表示走不通，找不到路

（二）广度/宽度优先搜索(breath first search(bfs)):

bfs解析：

找周围四个方向是否有一点是终点,如果没有,就继续找这四个点的周围四个点;
流程：先查找四个方向，再继续查找某一个方向的4个方向

步骤：
	1：将起点添加到路径
	int i=0;
	2：while(i<路径的长度)
	{
		1：取出路径的第一个点（x,y)
		2：将第一个点从路径中移除
		3：判断当前x,y是否是终点，如果是，找到一条路，
		4：如果不是终点，将周围四个能走的点加入到路径中
		i++;
	}
	3：

dfs和bfs算法c++实现
1.1：点的结构体

struct Point
{
	int x;
	int y;
	Point(int x, int y)
		:x(x),
		y(y)
	{

	}
};

1.2 BFS 构建WayPoint

struct WayPoint
{
	int pre;//当前点的上一个分支对应在vector的下标
	Point point;//当前点的坐标
	WayPoint(int pre, Point point)
		:pre(pre),
		point(point)
	{

	}
};

2：定义数据类型

//1.定义一个vector,保存路径
vector<Point> path;

//2.定义一个vector,保存最短路径
vector<Point> minPath;

//3.定义一个最短路径的长度
int minStep = -1;

//上下左右的偏移量
int nextxy[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

3.：方法函数
3.1：判断某个点是否可以走

bool checkPoint(Map map, Map flagMap, int x, int y)
{
	//1.越界
	if (x < 0 || x >= map.getRow() || y < 0 || y >= map.getLine())
		return false;
	//2.走过
	if (1 == flagMap.getXY(x, y))
		return false;
	//3.障碍物
	if (1 == map.getXY(x, y))
		return false;
	return true;
}

3.2dfs深度优先搜索

bool dfs(Map map, Map& flagMap, int x, int y, int endx, int endy)
{
	//4.判断是否是终点
	if (x == endx && y == endy)
	{
		return true;
	}
	//5.遍历周围四个点(上下左右)
	for (int i = 0; i < 4;i++)
	{
		int xx = x + nextxy[i][0];//x
		int yy = y + nextxy[i][1];//y
		if (checkPoint(map, flagMap, xx, yy))//判断这个点是否走得通
		{
			//6.将该点放入path,标记为走过
			path.push_back(Point(xx, yy));
			flagMap.setXY(xx, yy, 1);
			//7.递归这个点
			if (dfs(map, flagMap, xx, yy, endx, endy))//在某一分支找出了出口
			{
				return true;
			}
			//8.将该点移出path,标记为没走过
			path.pop_back();
			flagMap.setXY(xx, yy, 0);
		}
	}
	return false;//表示找不到出口
}

3.3通过dfs查找最短路径(深度优先搜索)

void dfsMin(Map map, Map& flagMap, int x, int y, int endx, int endy)
{
	//4.判断是否是终点
	if (x == endx && y == endy)
	{
		//判断当前path的长度是否小于最短
		if (path.size() < minStep || -1 == minStep)
		{
			//如果小于最短,path就是最短路径
			minPath = path;
			minStep = path.size();//长度用当前最短路径的长度赋值
		}
		return;
	}
	//5.遍历周围四个点(上下左右)
	for (int i = 0; i < 4; i++)
	{
		int xx = x + nextxy[i][0];//x
		int yy = y + nextxy[i][1];//y
		if (checkPoint(map, flagMap, xx, yy))//判断这个点是否走得通
		{
			//6.将该点放入path,标记为走过
			path.push_back(Point(xx, yy));
			flagMap.setXY(xx, yy, 1);
			//7.递归这个点
			dfsMin(map, flagMap, xx, yy, endx, endy);//在某一分支找出了出口
			//8.将该点移出path,标记为没走过
			path.pop_back();
			flagMap.setXY(xx, yy, 0);
		}
	}
	return;//表示找不到出口
}

3.4 通过bfs查找最短路径(广度/宽度优先搜索)

bool bfs(Map map, Map& flagMap, int startx, int starty, int endx, int endy)
{
	vector<WayPoint> queue;//存放所有遍历过的点的信息
	//1.将起点放入,并标记为走过
	queue.push_back(WayPoint(-1,Point(startx,starty)));
	flagMap.setXY(startx, starty, 1);
	int idx = 0;//下标
	while (idx < queue.size())//当前下标<整个队列的长度
	{
		Point point = queue[idx].point;//拿出当前要遍历这个点
		//判断这个点是否是终点
		if (point.x == endx && point.y == endy)
		{
			//找出最短路径
		    //queue:WayPoint
			//path:Point
			while (idx != -1)
			{
				Point point = queue[idx].point;
				path.push_back(point);
				idx = queue[idx].pre;
			}
			//进行path的翻转
			std::reverse(path.begin(),path.end());//1.begin  2.end
			return true;
		}
		//将这个点的周围四个点放入queue里面
		for (int i = 0; i < 4;i++)
		{
			int xx = point.x + nextxy[i][0];
			int yy = point.y + nextxy[i][1];
			if (checkPoint(map, flagMap, xx, yy))//判断该点是否能走通
			{
				flagMap.setXY(xx, yy, 1);
				queue.push_back(WayPoint(idx,Point(xx,yy)));
			}
		}
		idx++;//下一次遍历下一个点
	}

	return false;//没有找到
}

4:查找路径（深度优先搜索） 和（广度/宽度优先搜索）
1：深度优先搜索(dfs)

bool findPath(Map map,Map& flagMap,int startx,int starty,int endx,int endy)
{
	//1.将起点放入path中
	path.push_back(Point(startx, starty));
	//2.将起点标记为走过
	flagMap.setXY(startx, starty, 1);
	
	//1.dfs查找一条路径
	if (dfs(map, flagMap, startx, starty, endx, endy))
	{
	return true;
	}
	return false;
	
	//2.dfsmin查找一条最短路径
	dfsMin(map, flagMap, startx, starty, endx, endy);
	if (minPath.size() > 0)
	{
		minPath.swap(path);
		return true;
	}

	
}

2:广度/宽度优先搜索(bfs)

//1.将起点放入path中
	path.push_back(Point(startx, starty));
	//3.将起点标记为走过
	flagMap.setXY(startx, starty, 1);
	
//2.通过bfs查找最短路径
	if (bfs(map, flagMap, startx, starty, endx, endy))
	{
		return true;
	}
	return false;

（二）主函数测试

int main()
{
	//创建地图和标记地图
	int data[10][10] =
	{
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
		{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
	};
	Map map(10, 10, &data[0][0]);//寻路地图
	Map flagMap(10, 10);//标记地图
	map.draw();
	int startx, starty;//起始点
	cout << "请输入起始点" << endl;
	cin >> startx >> starty;
	int endx, endy;//结束点
	cout << "请输入结束点" << endl;
	cin >> endx >> endy;

	if (findPath(map,flagMap,startx,starty,endx,endy))
	{
		//遍历vector,将所有路径中的点一一变为2
		for (Point point: path)
		{
			//将point对应的点设置为2
			map.setXY(point.x, point.y, 2);
			map.draw();
		}
		cout << "Success!" << endl;
	}
	else
	{
		cout << "Failed!" << endl;
	}
	return 0;
}

地图文件数据创建：Map.cpp

#include "Map.h"
#include <string.h>
#include <iostream>
#include <windows.h>
using namespace std;
Map::Map(int row, int line, int *data)
	: row(row),
	  line(line)
{
	//申请二维数组的内存
	pMap = new int *[row]; //保存每一行的首地址
	for (int i = 0; i < row; i++)
	{
		pMap[i] = new int[line];
	}
	setData(data);
}

void Map::setData(int *data)
{
	//如果数据地址为nullptr,给数组的所有元素赋值为0
	if (nullptr == data)
	{
		for (int i = 0; i < row; i++)
		{
			//1.目的地址 2.值 3.字节数
			memset(pMap[i], 0, sizeof(int) * line); //将一段内存空间填入某个值
		}
	}
	else
	{
		for (int i = 0; i < row; i++)
		{
			memcpy(pMap[i], data, sizeof(int) * line);
			data = data + line; //data偏移一行
		}
	}
}

void Map::draw() //打印地图
{
	system("cls");
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < line; j++)
		{
			switch (pMap[i][j])
			{
			case 0:
				cout << "  ";
				break;
			case 1:
				cout << "墙";
				break;
			case 2:
				cout << "人";
				break;
			}
		}
		cout << endl;
	}
	Sleep(300);
}

Map::~Map()
{
}