BFS
队列实现
model
// 队列init
int queue[const int len]; // 定义队列
int head = 0, tail = 0; // 队头head出队， 队尾tail入队
queue[tail++] = x; // 初始值入队，队尾入队
while(head != tail){ // 当队列不为空–>判空条件 head == tail
int x = queue[head++]; // 队头出队
// 当前x邻近元素入队
/*
元素操作
e.g. bfs操作可以定义dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}实现上下左右的遍历
再通过if判断当前(i, j)是否合法以及grid对应值是否合法，进行更新
queue[tail++]入队
… …
*/ }
例题-994 腐烂的橘子 mid
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值 0 代表空单元格；
- 值 1 代表新鲜橘子；
- 值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
depth用于记录当前橘子腐烂到多少分钟
由于bfs橘子腐烂上下左右扩散，每次扩散分钟数加一
所以最后一次更新ans即扩散最大分钟数
const int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int orangesRotting(int** grid, int gridSize, int* gridColSize) {
int m = gridSize, n = gridColSize[0];
int queue[m*n];
int depth[m*n];
memset(depth, 0, sizeof(depth));
int head = 0, tail = 0;
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(grid[i][j] == 2){
queue[tail++] = i*n + j;
}
}
}
int ans = 0;
while(head != tail){
int x = queue[head++];
int r = x/n, c = x%n;
for(int i = 0; i<4; i++){
int nr = r+dirs[i][0];
int nc = c+dirs[i][1];
if(nr>=0 && nr<m && nc>=0 && nc<n && grid[nr][nc] == 1){
grid[nr][nc] = 2;
int code = nr*n+nc;
queue[tail++] = code;
depth[code] = depth[x]+1;
ans = depth[code];
}
}
}
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(grid[i][j] == 1)return -1;
}
}
return ans;
}
例题-207 课程表 mid
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses – 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
本质：拓扑序列是否存在回路
方法1：BFS+邻接矩阵
bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {
// 入度数组==第i个课程需要的先行课数目
int* indegree = calloc(numCourses, sizeof(int));
// 用邻接矩阵（n*n）表示图结构，init
int** matrix = malloc(sizeof(int*)*numCourses);
for(int i = 0; i<numCourses; i++){
matrix[i] = calloc(numCourses, sizeof(int));
}
// 邻接矩阵中matrix[i][j]表示i->j的弧边存在与否
for(int i = 0; i<prerequisitesSize; i++){
// x->y
int x = prerequisites[i][1]; // 先行课
int y = prerequisites[i][0]; // 当前的课
matrix[x][y] = 1; // 存在
indegree[y]++; // 当前课的先行课+1
}
// bfs遍历
int queue[numCourses] = {};
int head = 0, tail = 0;
for(int i = 0; i<numCourses; i++){
if(indegree[i] == 0){
queue[tail++] = i; // 入度为0的元素入队
}
}
while(head!=tail){
int cur = queue[head++];
for(int i = 0; i<numCourses; i++){ // 扫描矩阵是否存在边
if(matrix[cur][i]){ // 存在
indegree[i]–; // 删除该边，入度-1
if(indegree[i] == 0){ // 当入度为0时，加入队列
queue[tail++] = i;
}
}
}
}
for(int i = 0; i<numCourses; i++){
if(indegree[i])return false; // 存在回路
}
return true;
}
DFS
栈实现
三部曲 –> 和回溯三部曲类似
回溯算法（C）-CSDN博客
回溯型dfs
model
// step1- init
ans; path; ansTop; pathTop;
void dfs(paras){
// step2- 终止条件
if(…){……}
// step3- dfs
for(int i = …;…;i++){
// push
// dfs
// pop
}
}
例题-797 所有可能路径 mid
给你一个有 n 个节点的 有向无环图（DAG），请你找出从节点 0 到节点 n-1 的所有路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
示例 1：
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** ans;
int stk[15];
int stkSize;
void dfs(int x, int n, int** graph, int* graphColSize, int* returnSize, int** returnColumnSizes){
if(x == n){
int* tmp = malloc(sizeof(int)*stkSize);
memcpy(tmp, stk, sizeof(int)*stkSize);
ans[*returnSize] = tmp;
(*returnColumnSizes)[(*returnSize)++] = stkSize;
return;
}
for(int i = 0; i<graphColSize[x]; i++){
int y = graph[x][i];
stk[stkSize++] = y;
dfs(y, n, graph, graphColSize, returnSize, returnColumnSizes);
stkSize–;
}
}
int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
stkSize = 0;
stk[stkSize++] = 0;
ans = malloc(sizeof(int)*16384);
*returnSize = 0;
*returnColumnSizes = malloc(sizeof(int)*16384);
dfs(0, graphSize-1, graph, graphColSize, returnSize, returnColumnSizes);
return ans;
}
普通dfs –> 只遍历，不回溯
model
dfs(){
if(){} // 边界条件返回
// 标记(x, y)已访问
// 对四个方向，上下左右，遍历dfs（合法）
}
例题-200 岛屿数量 mid
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出：1
void dfs(char** grid, int i, int j, int rnum, int cnum){
if(i<0 || i>=rnum || j<0 || j>= cnum || grid[i][j] != '1')return;
grid[i][j] = '2';
dfs(grid, i+1, j, rnum, cnum);
dfs(grid, i-1, j, rnum, cnum);
dfs(grid, i, j+1, rnum, cnum);
dfs(grid, i, j-1, rnum, cnum);
}
int numIslands(char** grid, int gridSize, int* gridColSize) {
int rnum = gridSize, cnum = gridColSize[0];
int ans = 0;
for(int i = 0; i <rnum; i++){
for(int j = 0; j<cnum; j++){
if(grid[i][j] == '1'){
dfs(grid, i, j, rnum, cnum);
ans++;
}
}
}
return ans;
}
例题-LCR 105 岛屿的最大面积 mid
给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
输入: grid = [[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]]
输出: 6
解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1。
#define MAX(a, b)((a)>(b)?(a):(b))
void dfs(int** grid, int m, int n, int i, int j, int* sum){
if(i<0 || i>=m || j<0 || j>=n || grid[i][j] != 1)return;
grid[i][j] = 2;
(*sum)++;
dfs(grid, m, n, i+1, j, sum);
dfs(grid, m, n, i-1, j, sum);
dfs(grid, m, n, i, j+1, sum);
dfs(grid, m, n, i, j-1, sum);
}
int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
int ans = 0;
int m = gridSize, n = gridColSize[0];
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(grid[i][j] == 1){
int sum = 0;
dfs(grid, m, n, i, j, &sum);
ans = MAX(ans, sum);
}
}
}
return ans;
}
