广度优先搜索和深度优先搜索是根据图来搜索的算法，或者说是对图进行遍历的算法，而图是一种数据结构。如下的图：
广度优先搜索(BFS)的搜索思想是先确定图中的一个节点为起始节点，然后从这个起始点开始搜索和它相邻的每个点，然后再以这些搜索到的相邻的节点向外搜索和他们相邻的其他节点，每个搜索过的节点都要进行标记，标记过的节点就不再搜索，每个节点都有自己距离起始节点的长度，这个长度以与他相邻的上一个节点的长度+1；搜索直到所有可搜索的节点全部遍历，得到所有节点到起始节点的距离。
广度优先搜索用队列实现：
把起始节点插入队列；每次从队列的头部取出一个元素，查看这个元素所有的下一级相邻元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱；找到要找的元素时结束，或者队列为空即所有元素全部遍历完；下面是一个运用广度优先搜索处理的关于迷宫的问题：
#include <iostream> #include <queue> #include <algorithm> #include <string.h> using namespace std; bool vis[201][201];//记录访问过没有 bool取值false和true，0为false，非0为true。 int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; char Map[201][201]; int N,M; int sx,sy,ex,ey; struct Step { int x; int y; int step; }; struct comp { bool operator() (Step &a,Step &b) { return a.step > b.step; } }; bool panduan(int x,int y) { if( x<1 || y<1 || x>N || y>M ) return false; else if( vis[x][y] ) return false; else if( Map[x][y] == '#' ) return false; else return true; } int bfs() { priority_queue< Step, vector<Step>, comp > q; Step s0,s_next; memset(vis,0,sizeof(vis)); s0.x = sx; s0.y = sy; s0.step = 0; vis[sx][sy] = true; q.push(s0); while( !q.empty() ) { s0 = q.top(); q.pop(); if( s0.x == ex && s0.y == ey) return s0.step; for(int i=0; i<4; i++) { int nx = s0.x + dx[i]; int ny = s0.y + dy[i]; if( panduan(nx,ny) ) { s_next.x = nx; s_next.y = ny; s_next.step = s0.step + 1; vis[nx][ny] = true; q.push( s_next ); } } } return -1; } int main() { cin>>N>>M; for(int i=0; i<N; i++) for(int j=0; j<M; j++) { cin>>Map[i][j]; if( Map[i][j] == 'G' ) { ex = i; ey = j; } else if( Map[i][j] == 'S' ) { sx = i; sy = j; } } int s = bfs(); cout<<s<<endl; return 0; }深度优先搜索的思路也是先从起始点出发，先对他下一层其中一个邻接点进行深搜，同样也是再找邻接点向下一层再进行深搜，深到底时不能再往下深时，就要回溯了，回溯是从下往上回溯的。从下向上每回溯到上一层，再找同一层的另一个邻接点进行深搜。当一个点所有的邻接点都深搜过了，标记这个点搜索完毕，不再对此深搜。深搜比广搜的优点是深搜能记住搜索路径。
深度优先遍历图的方法是，从图中某顶点v出发：
访问顶点A；依次从A的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和A有路径相通的顶点都被访问若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。深搜可以用递归或堆栈处理： DFS–基本入门模板 和 递归例题
