参考文章：/CyC/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%90%9C%E7%B4%A2.md

广度优先搜索（BFS）

广度优先搜索是按层来处理顶点的，距离开始点最近的那些顶点首先被访问，而最远的那些顶点则最后被访问。BFS的代码使用了一个队列。搜索的步骤：

首先选择一个顶点作为起始顶点，将起始顶点放入队列中从队列首部选出一个顶点，将与之相邻并且没有被访问的结点依次加入到队列的队尾，然后访问这些与之相邻并且没有被访问过的结点，将队列队首的结点删去。按照步骤2处理队列中下一个结点，直到找到要找的结点或者队列中没有结点结束。

void BFS(){定义队列;定义备忘录，用于记录已经访问的位置；判断边界条件，是否能直接返回结果的。将起始位置加入到队列中，同时更新备忘录。while (队列不为空) {获取当前队列中的元素个数。for (元素个数) {取出一个位置节点。判断是否到达终点位置。获取它对应的下一个所有的节点。条件判断，过滤掉不符合条件的位置。新位置重新加入队列。}}}

我们用一道LeedCode上面的题目讲解，题目位置：

https://leetcode-/problems/shortest-path-in-binary-matrix/

这里我们需要注意三点：

需要一个队列，来记录下一次访问的结点，因为该队列是记录结点位置的（访问结点的下标），如果一维数组可以搞定，定义个int queue[QUEUE_SIZE]，如果是二维，定义int queue[QUEUW_SIZE][2].需要一个备忘录，记录已经被访问的结点，备忘录用数组表示每一层结点数就是可以访问的结点，这里题目是 8 个方向上的单元格

#include <stdio.h>#include <string.h>#include <stdlib.h>#define QUEUE_SIZE 10001int BFS(){int grid[3][3] = {{0,0,0},{1,1,0},{1,1,0}};int gridSize=3;int ans=0; /*判断边界条件，即结束条件*/if(grid[gridSize-1][gridSize-1]==1 || grid[0][0]==1)return -1;/* 获取队列 */if(gridSize==1)return 1;int m=gridSize,n=m*m,front=0,rear=0,pre_rear=0,cnt=1;/* 设置队列 */ int **cularr = (int **)malloc(sizeof(int)*n);for(int i=0;i<n;i++){cularr[i]=(int *)malloc(sizeof(int)*2);}/* 将首结点入队 并将其设置已经访问过了*/cularr[rear][0]=0;cularr[rear++][1]=0;/*将其修改为1 表示这个数据不需要在访问 */grid[0][0]=1;/* 根据题目要求广度优先都要有8个结点 */int temp[8][2] = {{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1},{-1,0}};while(front<rear){pre_rear = rear;/* 遍历每一层上的结点 */while(front<pre_rear){for(int i=0;i<8;i++){int x = cularr[front][0]+temp[i][0];int y = cularr[front][1]+temp[i][1];//此时是最后一个结点if((m-1==x)&&(m-1==y)){return cnt+1;}//将没有访问符合的符合条件的加入队列中if(x<m && x>=0 && y<m && y>=0 && grid[x][y]==0){cularr[rear][0]=x;cularr[rear++][1]=y;grid[x][y]=1;}}front++; //获取下一个队首元素}cnt++;//广度优先遍历了一层，要加1}return -1;}int main(void){int num = BFS();printf("%d\n",num);return 0;}

深度优先遍历（DFS）

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。

而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种可达性问题。

在程序实现 DFS 时需要考虑以下问题：

栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。每个结点有多少个子树（也就是一个结点遍历完，深度优先遍历时，有几个可选的结点可以遍历，比如上图的0，可以有1、2、5、6四个结点可以选择）

我们用LeedCode上面的题目来讲解：

695. 岛屿的最大面积

#include <stdio.h>#include <stdlib.h>int dfs(int **grid,int gridSize,int *gridColSize,int row,int col){//条件判断if(row<0 || row>=gridSize || col<0 || col>=gridColSize[0] || grid[row][col]==0){return 0;}//将1置为0，表示已经访问过该结点grid[row][col]=0;//遍历所有可以遍历的情况return 1+dfs(grid,gridSize,gridColSize,row,col+1)+dfs(grid,gridSize,gridColSize,row,col-1)+dfs(grid,gridSize,gridColSize,row+1,col)+dfs(grid,gridSize,gridColSize,row-1,col);}int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize) {int area=0,max=0,i,j;for(i=0;i<gridSize;i++){for(j=0;j<gridColSize[0];j++){area = dfs(grid,gridSize,gridColSize,i,j);max = max>area?max:area;}}return max;}int main(void){int grid[][13] = {{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}};int gridColSize =13;int **p = malloc(sizeof(int)*8);for(int i=0;i<8;i++){p[i]=grid[i];}int max = maxAreaOfIsland(p,8,&gridColSize);printf("max=%d\n",max);return 0;}

求岛屿最大面积，也就是从一个结点出发，我们按前后左右方向走，可以走的最大格子数（可达最大区域）。

我们访问过一个位置后，使用深度优先遍历的话，我们可以有四个选择，也就是水平或者竖直的四个方向上，这对应深度优先遍历，就是每个结点都有四个子树。

对于可以访问的结点，访问过后，我们将其值1置为0，表示已经访问过了（0在这个题目当中不需要访问）。

对于栈，这题我们用递归，因为有四个选择，我们在递归时，需要加上四个dfs函数。

结果：

回溯法

Backtracking（回溯）属于 DFS。

普通 DFS 主要用在 可达性问题 ，这种问题只需要执行到特点的位置然后返回即可。而 Backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,‘b’,‘c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径, 选择列表)撤销选择以上三种定义：1、路径：也就是已经做出的选择2、选择列表：也就是当前可以做的选择3、结束条件：也就是到达决策树底层，无法再做选择的条件

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>/*** 本解答模仿 /wuyuegb2312/p/3273337.html 编写* 本解答以供自己学习提升和分享 MasterXU*/static char g_ch[10][4] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz",};static int g_total[10] ={0,0,3,3,3,3,3,4,3,4}; /*** number: 输入待转换数字* answer：解空间,存放路径上每个节点的选择,由于是递归实现 需要保存1条路径节点即可* index: 当前深度* depth: 最大路径深度* ans: 返回结果* pathIdx:当前路径编号*/void recursive(char *number, int *answer, int index, int depth, char **ans, int *pathIdx){//当当前深度等于最大深度时，表示此时DFS遍历完一条路径了，需要将这条路径的元素记录if(index == depth){//分配存放该路径上元素的内存ans[*pathIdx] = (char *)malloc((depth+1)*sizeof(char));//获取该路径每层的元素，number[i]-'0'表示选的层数，answer[1]表示选该层的元素for(int i=0;i<depth;i++){ans[*pathIdx][i]=g_ch[number[i]-'0'][answer[i]];}ans[*pathIdx][depth]='\0';//下一次记录下一路径的元素(*pathIdx)++;//返回表示该路径已经记录完毕return;}/*index+1：表示遍历下一层answer[index+1]++：遍历下一个兄弟结点 */for(answer[index]=0;answer[index]<g_total[number[index]-'0'];answer[index]++){recursive(number,answer,index+1,depth,ans,pathIdx);}}/*** Note: The returned array must be malloced, assume caller calls free().*/char ** letterCombinations(char * digits, int* returnSize){int a[100] = {0}; //记录深度遍历每条路径上结点的位置int depth = strlen(digits); //深度优先遍历的最大深度int num = (int)pow(4,depth); //深度优先遍历的最多路径个数*returnSize = 0; //路径计数if(depth == 0)return NULL;char **ans = (char **)malloc(num*sizeof(char *));recursive(digits,a,0,depth,ans,returnSize);return ans;}int main(void){char *digits = "23";int returnSize =0;char **ans = letterCombinations(digits,&returnSize);printf("returnSize = %d\n",returnSize);for(int i =0;i<returnSize;i++){puts(ans[i]);}return 0;}