博客

BFS能够求得最短路径，因为BFS每进行一次相当于当前的路径长度。对于一个N*N矩阵，BFS最多运行n*n次。



深度优先搜索相当于一个人在走迷宫，广搜相当于是无穷人沿着不同方向走（因为每条路都同时有人走）。

DFS相当于是一个下压栈。是先进后出的原则（如果找不到，往回走，直到回到有路的地方）（DFS隐式使用了栈）

BFS使用队列，按照与起点的距离来搜索。

BFS使用一个队列来保存已经被标记但是它的邻接表还没有被访问的顶点。先把起点加入队列，然后重复以下操作直到队列为空。

1、取队列中下一个顶点V并标记它

2、把和V相邻的所有没有标记的顶点加入队列。

BFS的标记edgeto代表了它的上一个节点，它的上一个节点一定只有一种情况，代表了最短解（不一定是唯一的），因为从1，1辐射出来的点不断地在刷最短路径。

深度优先搜索优先寻找离起点最远的顶点，广度优先搜索最先找最近的顶点

深度优先找到的必然是一个连通分量（因为走到死胡同为止）

HDOJ1240

BFS最短路径

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int n;
const int size =12;
int matrix[size][size][size];
int step[size][size][size];
int sx,sy,sz,dx,dy,dz;
int tx[]={
  1,-1,0