1. DFS（深度优先遍历）

理论介绍

DFS属于图算法的一种，是针对图和树的遍历算法。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆或栈来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入，每个节点只能访问一次。

博主个人理解

DFS（深度优先遍历），是图论中的一种遍历方式，我们可以认为DFS是一个执着的人，不到南墙不回头，他会一直走到头，然后回溯，空讲比较抽象，我们直接来看DFS的一个应用，排列数字，如这样一个例题

那么他是怎样去遍历呢？ 以n=3为例，从根节点开始，第一层有三种选择方式分别是1，2，3，那么对应第二层就有2，3 或者1，3或者1，2这几种选择，可以看下面这张图

他的遍历是将每一种可能走到头，然后回溯的，这也是DFS的标志，执着！

代码实现

import java.util.*;
public class Main{static int N = 10,n;static int[] path = new int[N];//记录路径static boolean st[] = new boolean[N];//记录数字是否已被使用public static void main(String[] args){Scanner scan = new Scanner(System.in);n = scan.nextInt();dfs(0);//从第0层开始遍历}public static void dfs(int u){if(u == n){//遍历至最后一层for(int i = 0;iSystem.out.print(path[i]+" ");//输出结果之一}System.out.println();return;//结束，并回溯}for(int i = 1;i<=n;i++){if(!st[i]){//当前数字未被使用过path[u]=i;//记录当前这一层的数字st[i]=true;//将这个数字表示已使用过，这样接下来就不会再被使用dfs(u+1);//遍历下一层st[i]=false;//恢复现场}}}
}

主要解题思路，从0层开始以dfs的方式去遍历，如果判断到了最后一层则回溯，在每一层判断时，先枚举数字是否被使用过，如果未被使用过，则将其记为本层使用的数字，并标记使用过了，同时遍历下一层，注意要恢复现场，否则会对其余遍历造成影响。

2.BFS（宽度优先遍历）

理论介绍

广度优先搜索（也称宽度优先搜索）是连通图的一种遍历算法，也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和广度优先搜索类似的思想。属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
博主个人理解

BFS是比较贪心且懒惰的一个人，他会优先去搜索自己周围最近的所有单位，直到最近的都被找过了，去找下一接近的，直至最后，也因为他的懒惰，所以这种算法使用于最短路径问题！还是直接来例题 走迷宫

读题可知，要求的是所有出路中最短的那一条，这正是BFS的适用解，我们看一下遍历过程

要注意的是 每次拓展的是，能在规定步数内走到的所有点位！

代码实现

import java.io.*;
public class Main{static int N = 110;static int hh,tt,n,m;static int[][] g = new int[N][N];//用来存储迷宫地图static int[][] d = new int[N][N];//用来存储走的距离static PII[] q = new PII[N*N];//用来放每个点的下标public static int bfs(){hh = 0;tt = -1;d[0][0] = 0;//左上角，因为是起点，初始化为0q[++tt] = new PII(0,0);int[] dx = {-1,0,1,0};//上(-1,0) 下(1,0)int[] dy = {0,1,0,-1};//左(0,-1) 右(0,1)，这里是图论中常用的坐标移动方法while(hh<=tt){//队列不空，说明还没有遍历过所有点PII t = q[hh++];//取出队头for(int i = 0;i < 4;i++){int x = t.first+dx[i];int y = t.second+dy[i];//这里是遍历四个方位if(x>=0 && x=0 && y//解释下条件     x移动后没有越界    y移动后没有越界  当前点位还没来过  这个点是通的，-1表示此路不通d[x][y]=d[t.first][t.second]+1;q[++tt] = new PII(x,y);//移动后的点符合最近且为遍历过，且不越界的条件，入队！}}}return d[n-1][m-1];}public static void main(String[] args)throws IOException{BufferedReader re = new BufferedReader(new InputStreamReader(System.in));//快读BufferedWriter wt = new BufferedWriter(new OutputStreamWriter(System.out));//快写String[] s = re.readLine().split(" ");n = Integer.parseInt(s[0]);m = Integer.parseInt(s[1]);for(int i = 0 ; i < n ;  i ++ ){String[] st = re.readLine().split(" ");for(int j = 0 ; j < m ;j ++ ){g[i][j] = Integer.parseInt(st[j]);//读入迷宫地图d[i][j] = -1;//将所有距离设为-1}}System.out.println(bfs());wt.close();}
}
class PII{//存储结构，就是存的坐标，因为要存在队列里，所以不能直接写，要包装以下int first,second;public PII(int first,int second){this.first  = first;this.second = second;}
}

主要解题思路，以bfs的方式遍历整个地图，用d数组来记录走了多远，那么d[n][m]就是最短距离，先遍历起点，然后按照其可以移动的位置，将所有可能存入队列中，遍历队列里的每一个点，并继续添加，直至所有点都被遍历完成，这样得出最后的答案。