BFS求解迷宫问题

BFS求解迷宫问题

BFS解决迷宫问题

广度优先搜索

定义BFS遍历过程算法实现

算法思想图的广度优先搜索算法—邻接矩阵 求解迷宫问题

案例分析代码实现

广度优先搜索 定义

广度优先搜索，又称宽度优先搜索，广度优先搜索是一层一层访问的，类似于树的层次遍历，图的顶点之间是多对多的关系，相对于出发点由近及远地访问，直到所有的结点都被访问。

BFS遍历过程

从某顶点开始出发，依次访问未被访问的邻接点。按照“先被访问顶点的邻接点先访问”的次序，依次访问这些邻接点的邻接点，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未曾被访问，则另选一个未被访问的顶点v作为出发点，重复上述过程，直至图中所有的顶点都被访问完

算法实现 算法思想

广度优先搜索遍历体现先进先出的特点，用队列体现。
访问v后，再访问v的相邻结点V1,V2一直到Vk,最后个再按照V1,V2一直到Vk 这个次序依次访问它们的相邻点，V1之前较先访问，V1的相邻点也会较V2一直到Vk的相邻点先访问，所以这里具有了先进先出的特点，因为可以队列保存已经访问过的顶点。

设置一访问标志数组，在访问之前，将每个顶点的标志位设为false,如果某个顶点被访问了，则数组相应位置置为ture。现在放置一个队列，每当访问一个顶点，就将这个顶点入队，当访问它的相邻点时，就将它出队。
最后遍历的结果为V1,V2,V3,V4,V5,V8,V5,V6,V7
遍历的结果不唯一，一结点的相同邻接点位置不唯一。

在有向图图的遍历中，由于具有单向性，会导致图不是强连通图或连通图，也就是有两个或两个以上的连通子图或强连通子图。如图2，具有两个连通分量，在最后，从第二个连通分量V5开始，再次进行广度优先遍历。

图的广度优先搜索算法—邻接矩阵

void BFSM(MGgrph *g,int k)//邻接矩阵
//从V0出发广度优先遍历图G
{
int i,j;
initqueue(Q);//初始化设置空队列Q
enqueue(&Q,k);//要访问我的结点进队列Q
printf("%s",G->vex[k].info);
visited[k]=TURE;
while(!=QueueEmpty(&Q))//队列不为空时
{
 i=dequeue(&Q);//队头元素v出队列
for(j=1;j<=G-n;;j++)
{
 if(G->edges[i][j]==1&&visited[j]==0)
 {
  printf("%c",G->vex[j].info);
  visited[j]=TURE;
  enqueue(&Q,j);//访问的Vj进队
 } 
}
}
}//

求解迷宫问题 案例分析

0 1 0 0 0 0
0 0 0 1 0 0
0 0 1 0 0 1
1 1 0 0 0 0
对于这样一个简单的迷宫，图中1表示障碍无法通行，要求求出从左上角起点开始到右下角的终点,寻求一条所需步数最短的路径，若有多条最优路线，则按照字典序D

为了简便，定义一个point类来存放每个顶点的数据。
设置移动过程中分别沿x,y方向的变量,定义一个dir[]数组存储运动过程中方向的变化，与坐标x,y的变化保持一一致。

struct point
{
	int x;
	int y;
	int step;
	string str;
};
queue r;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,-1,1,0 };
char dir[4] = { 'D','L','R','U' };

赋值起点的坐标信息，访问数组标志为1，起点已经被访问，入队。

	point start;
	start.x = startx;
	start.y = starty;
	start.step = 0;
	v[startx][starty] = 1;
	int flag = 0;
	r.push(start);

//对每个已访问的结点依次访问它的相邻顶点
		for (int k = 0; k <= 3; k++)
		{
			int tx, ty;
			string str1;
			tx = x + dx[k];
			ty = y + dy[k];
			str1 = str + dir[k];
			if (v[tx][ty] == 0 && a[tx][ty] == 0)
			{//该顶点不是障碍且未被访问
				point temp;//定义一个临时队列，用来与前面的队列进行合并
				temp.x = tx;
				temp.y = ty;
				temp.step = r.front().step + 1;
				temp.str = r.front().str +dir[k];
				r.push(temp);
				v[tx][ty] = 1;
			}

当起始结点的领边结点都被访问，起始结点出队。当队列不为空时，每次循环只需判断当前队列首顶点的值是否与输入的终点坐标的值相同。

		if (x == p && y == q)
		{
			flag = 1;//存在最优路径
			cout << r.front().step << endl;
			cout << r.front().str << endl;
			break;
		}

若不存在从起始到终点的路径,输出错误信息。

		if (flag == 0)
		cout << "no answer!" << endl;

代码实现

完整代码

#include
#include
#include
using namespace std;
int a[100][100], v[100][100];
struct point
{
	int x;
	int y;
	int step;
	string str;
};
queue r;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,-1,1,0 };
char dir[4] = { 'D','L','R','U' };
int main()
{
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			//scanf("%d" ,&a[i][j]);
			cin >> a[i][j];
	int startx, starty, p, q;
	cin >> startx >> starty >> p >> q;
	point start;
	start.x = startx;
	start.y = starty;
	start.step = 0;
	v[startx][starty] = 1;
	int flag = 0;
	r.push(start);
	while (!r.empty())
	{
		int x = r.front().x;
		int y = r.front().y;
		string str = r.front().str;
		if (x == p && y == q)
		{
			flag = 1;
			cout << r.front().step << endl;
			cout << r.front().str << endl;
			break;
		}
		for (int k = 0; k <= 3; k++)
		{
			int tx, ty;
			string str1;
			tx = x + dx[k];
			ty = y + dy[k];
			str1 = str + dir[k];
			if (v[tx][ty] == 0 && a[tx][ty] == 0)
			{
				point temp;
				temp.x = tx;
				temp.y = ty;
				temp.step = r.front().step + 1;
				temp.str = r.front().str +dir[k];
				r.push(temp);
				v[tx][ty] = 1;
			}
		}
		r.pop();
	}
	if (flag == 0)
		cout << "no answer!" << endl;
}

运行测试