目录
Depth First Search(dfs)代码（递归）代码（非递归）Breadth First Search(bfs)代码比较数据结构时间复杂度使用例题：岛的个数dfs实现（递归）bfs实现参考Depth First Search(dfs)
不管有多少条路，先一条道走到底，不断往下往后遍历，直到无路可走，再返回到上一个状态继续。常用递归实现，非递归常用栈存储待访问结点。使用栈的原因是栈是后进先出的，而dfs前次遍历到终点，下次迭代需要回到上一个状态。
bfs步骤：
不断递归，直到尽头。回溯到上一个可以继续的状态。
比如，现在有一个图，结点为 A,B,C,D,E,FA,B,C,D,E,FA,B,C,D,E,F。其中，AAA与B,C,DB,C,DB,C,D连接，BBB与E,FE,FE,F连接。CCC与G,HG,HG,H连接。
访问结点AAA，把AAA压入栈（此时栈：AAA）。继续向下访问BBB，BBB入栈（此时栈：B,AB,AB,A）继续向下访问EEE，EEE入栈（此时栈：E,B,AE,B,AE,B,A）EEE无法继续访问，EEE出栈（此时栈：B,AB,AB,A），返回到上一个可以继续向后访问的点BBB。继续向下访问FFF，FFF入栈（此时栈：F,B,AF,B,AF,B,A）。FFF无法继续访问，FFF出栈（此时栈：B,AB,AB,A），返回到上一个可以继续向后访问的点BBB。BBB的子结点已经全部被访问，无法继续向下访问，BBB出栈（此时栈：AAA），返回到上一个可以继续向后访问的点AAA。继续向下访问CCC，CCC入栈（此时栈：C,AC,AC,A）。不断重复。直到栈为空。
代码（递归）
int goal_x = 9, goal_y = 9;//目标的坐标，暂时设置为右下角int n = 10 , m = 10;//地图的宽高，设置为10 * 10的表格int graph[n][m]; //地图int used[n][m]; //用来标记地图上那些点是走过的int px[] = {-1, 0, 1, 0}; //通过px 和 py数组来实现左下右上的移动顺序int py[] = {0, -1, 0, 1};int flag = 0; //是否能达到终点的标志void DFS(int graph[][], int used[], int x, int y){// 如果与目标坐标相同，则成功if (graph[x][y] == graph[goal_x][goal_y]) {printf("successful");flag = 1;return ;}// 遍历四个方向for (int i = 0; i != 4; ++i) {//如果没有走过这个格子int new_x = x + px[i], new_y = y + py[i];if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && used[new_x][new_y] == 0 && !flag) {used[new_x][new_y] = 1;//将该格子设为走过DFS(graph, used, new_x, new_y);//递归下去used[new_x][new_y] = 0;//状态回溯，退回来，将格子设置为未走过}}}
代码出处
代码（非递归）
Class Node{Char data;Public Node(char c){this.data=c;}}public void dfs(){//DFS uses Stack data structureStack s=new Stack();s.push(this.rootNode);rootNode.visited=true;printNode(rootNode);while(!s.isEmpty()){Node n=(Node)s.peek();Node child=getUnvisitedChildNode(n);if(child!=null){child.visited=true;printNode(child);s.push(child);}else{s.pop();}}//Clear visited property of nodesclearNodes();}
代码出处
Breadth First Search(bfs)
访问一个结点时，先把可能的选择记录下来，可以按照顺序选择访问其中一个，再把它可能的选择记录下来，再返回选择另外一个，不断重复。bfs通常用队列存储可能的选择，因为队列先进先出的属性。
比如，现在有一个图，结点为 A,B,C,D,E,FA,B,C,D,E,FA,B,C,D,E,F。其中，AAA与B,C,DB,C,DB,C,D连接，BBB与E,FE,FE,F连接。CCC与G,HG,HG,H连接。
首先访问结点AAA，把可能的选择（B,C,DB,C,DB,C,D）记录下来，B,C,DB,C,DB,C,D入队，访问（BBB），BBB被访问后出队（此时队列：C,DC,DC,D），记录BBB可能的选择E,FE,FE,F，这里E,FE,FE,F入队（此时队列：C,D,E,FC,D,E,FC,D,E,F）。访问CCC（注：这里就相当于返回访问了，而不是继续沿着BBB的路径访问），CCC出队，记录CCC可能的选择，G,HG,HG,H入队（此时队列：D,E,F,G,HD,E,F,G,HD,E,F,G,H）。不断重复上面的步骤，也就是队列不断出队入队，直到队列为空。
代码
Class Node{Char data;Public Node(char c){this.data=c;}}public void bfs(){//BFS uses Queue data structureQueue q=new LinkedList();q.add(this.rootNode);printNode(this.rootNode);rootNode.visited=true;while(!q.isEmpty()){Node n=(Node)q.remove();Node child=null;while((child=getUnvisitedChildNode(n))!=null){child.visited=true;printNode(child);q.add(child);}}//Clear visited property of nodesclearNodes();}
代码出处
比较
数据结构
dfs：递归思想，栈结构。
bfs：队列结构
时间复杂度
大致相同。
使用
dfs适合目标明确，使用递归实现思路明确，但如果图深度过大，很可能会出现爆栈，需要改写成非递归形式。
bfs适合大范围寻找，使用队列存储待选择状态，不用递归实现，不会出现爆栈。
能用bfs尽量使用bfs，防止爆栈。
例题：岛的个数
LeetCode 200. 岛屿数量
dfs实现（递归）
int find_island(int *arr, int m, int n) {int res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (arr[i * n + j] == 1) {res++;infect(arr, i, j, m, n);}}}return res;}void infect(int *arr, int i, int j, int m, int n) {if (i < 0 || i >= m || j < 0 || j >= n || arr[i * n + j] != 1)return;arr[i * n + j] = 2;infect(arr, i - 1, j, m, n);infect(arr, i + 1, j, m, n);infect(arr, i, j - 1, m, n);infect(arr, i, j + 1, m, n);}
bfs实现
int bfs(int *arr, int m, int n) {int direction_x[] = {-1, 1, 0, 0};int direction_y[] = {0, 0, -1, 1};int res = 0;bool visited[m*n];memset(visited, false, sizeof(visited));queue<int> q;int x, y;int xx, yy;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (arr[i * n + j] == 1 && !visited[i * n + j]) {q.push(i);q.push(j);visited[i * n + j] = true;res++;while (!q.empty()){x = q.front();q.pop();y = q.front();q.pop();for (int k = 0; k < 4; k++){xx = x + direction_x[k];yy = y + direction_y[k];if (xx < 0 || xx >= m || yy < 0 || yy >= n)continue;if (arr[xx * n + yy] == 1 && !visited[xx * n + yy]) {visited[xx * n + yy] = true;q.push(xx);q.push(yy);}}}}}}return res;}
参考
搜索思想——DFS & BFS（基础基础篇）
Leetcode 200 Number of Islands 岛的个数
Introduction to Graph with Breadth First Search(BFS) and Depth First Search(DFS) Traversal Implemented in JAVA
