bfs算法思想

通常利用队列实现：

Q={初始状态start};
标记start为已访问;
while(Q非空)
{
队首元素t出队列;
if(t为目标状态){算法结束;}
所有与 t 相邻 的 未访问 的状态next入队列
标记next为已访问;
}

bfs算法大致实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<string.h>
#define N 1000
using namespace std;

int maps[N][N];	//存储地图，具体维度根据题意
int visit[N][N];	//记录状态是否访问，具体维度根据题意
int step[4][2] = { {-1,0},{1,0} ,{0,-1},{0,1} };	//搜索的四个方向，具体根据题意

int r, c;
int x, y, m, n;	//记录初始状态，和目标状态
struct Node	//定义状态结构体，用于保存于队列中 
{	
	int val;
	Node* pre;	//用于记录搜索路径
	Node(int val, int y, int t, int f) { this->val = val; }
};
void input()
{
	//freopen("in.txt", "r", stdin);
    scanf(...x,y,m,n);	//读入初始状态，目标状态
	scanf(...maps);	//构建图
	
}
void init()
{
	memset(state, 0, sizeof(state));//初始化访问状态
}

Node* bfs()
{
	init();	//初始化访问状态
	queue<Node*> q;
    //定义初状态，并且入队列
	Node* p = new Node(x, y, t, f);
	p->pre = NULL;
	q.push(p);
    //队列循环
	while (!q.empty())
	{
        //取出一个元素
		Node* t = q.front();
		q.pop();
		if (该元素是目标状态)
            return t;//是则搜索结束
		for (int i = 0; i < 4; i++)	//向各个方向进行搜索
		{
            
            if (搜索不越界 && 图中可行 && 状态未访问) {
			Node* p = new Node(value);//创建当前状态结构体
			p->pre = t;	//记录上一状态，用于输出搜索路径(可选)
			visit[...] = 1;	//标记搜索状态
			q.push(p);//重新入队列
		}
	}
	return NULL;
}
//利用栈，输出搜索路径
void print_ans(Node* p)
{
	stack<Node*> s;
	while (p != NULL) {
		s.push(p);
		p = p->pre;
	}
	while (s.size()!=0) {
		p = s.top();
		s.pop();
		printf(p);
	}
}
int main()
{
	input();
	Node* ret = bfs();
	if (ret != NULL)print_ans(ret);
	else printf("No Solution Possible\n");
	return 0;
}