这道题的原址:http://blog.csdn.net/johsnows/article/details/52997282
BFS是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
--------百度百科
搜索其实算一种暴力枚举的算法，不过这种暴力枚举是一种有条理性的暴力枚举， 更容易控制以及实现。它在求最短路以及遍历图或树的时候会用到。
说它是一种暴力枚举的算法是因为，如同百科提到的，它在搜索的时候仍然会遍历整张图中的所有节点，而它的条理性则体现在它用一个队列记录每一步搜索的状态，每一步新加入的状态都会加入队列，用于下一次搜索，并且状态会被继承。这种在图上实现的搜索不仅容易实现，也容易记录每一步的状态，用于求出答案（如最短路）。
建图方式：
邻接矩阵：二维数组： a[x][y]。x表示横坐标，y表示纵坐标，a[x][y]即代表这个点的状态。
邻接表： 指针数组：
[cpp] view plain copy struct ljb { int y; int z; }*a[x];
当题目所给的图过大，横纵坐标的最大值超过二维数组能开的空间时，可以使用邻接表。a[x]代表每一行的头结点。列和状态用链表的结点记录，挂在对应行的头结点之后。这样可以存下一个足够大的图，当然操作起来会更麻烦。
用于下一步搜索的next数组:
[cpp] view plain copy int next[4][2]={{0,1}, {1,0}, {0,-1}, {-1, 0}};
每一行的值分别代表向上右下左走一步，这样可以直接用一层for来实现向下一步搜索。
如dx=x+next[i][0], dy=y+next[i][1];
另外虽然是枚举，但是已经走过点应当避免重复枚举，所有用一个book[x][y]数组记录该点是否已经走过。
下面通过一个简单的用bfs求解的问题来讲解
题目：给出一个长为n宽m的地图，起点x,y和终点sx,sy，以及M个障碍物（不能经过的点），问从起点到终点最少需要经过多少步数。
关于bfs的用法就在代码中具体述说了：
[cpp] view plain copy #include <iostream> #include <cstdio> using namespace std; const int maxn=1e3+5; bool book[maxn][maxn]; //记录是否已经走过这个点 int t[maxn][maxn]; //邻接矩阵 int n,m; int next[4][2]={{0,1}, {1,0}, {0,-1}, {-1, 0}}; struct p { int x; //横坐标 int y; //纵坐标 int s; // 当前步数 }a[maxn];//用队列记录将要搜索的点 int bfs(int x, int y, int sx, int sy) { int head, tail, i, j; head=tail=0; //队头队尾初始化为0 a[head].x=x; a[head].y=y; a[head].s=0;//将起点加入队列,队列头的点表示当前要走的点 tail++; while(head<tail) { if(a[head].x==sx && a[head].y==sy) //如果当前点就是终点，则返回这个点的步数 { return a[head].s; } int dx, dy; //表示当前的点能够走的点的坐标 for(i=0; i<4; i++) //枚举四个可以走的方向 { dx=a[head].x+next[i][0]; dy=a[head].y+next[i][1]; if(dx>=0 && dx<=n && dy>=0 && dy<=m && t[dx][dy]!=-1) // 如果这个可以走的点不在图中或者是障碍物就不进行搜索，即不加入队列 if(book[dx][dy]==0 ) //book数组等于0表示这个点之前没有搜索过，可以走 { a[tail].x=dx; a[tail].y=dy; a[tail].s=a[head].s+1; //将这个点加入队尾，将在之后搜索，它的步数应当等于当前点所走的步数再加上一。 tail++; book[dx][dy]=1;//已经加入队列，标记已经搜索过，避免接下来重复搜索 } } head++;// <strong>让已经搜索过的点出队</strong>，容易忘记 } return -1; // 假如队列为空，即所有的点都已经搜索过了，但是并没有函数return结束，说明没能找到目标点，则返回-1表示不能到达 } int main() { int x, y, sx, sy; int M; scanf("%d%d%d%d%d%d", &n, &m, &x, &y, &sx, &sy); scanf("%d", &M); int i; memset(t, 0, sizeof(t)); //初始化图 for(i=0; i<M; i++) { int xx,yy; scanf("%d%d", &xx, &yy); t[xx][yy]=-1; //将障碍物标记为-1 } int ans=bfs(x,y,sx,sy); printf("%d\n", ans); return 0; }
转载于:https://www.cnblogs.com/CCCrunner/p/6444582.html
相关资源：人工智能代价树的广度优先搜索