图论

基础知识

存储方式

• 朴素：n*2数组表示
• 邻接矩阵：n*n数组
• 邻接表：数组加链表

DFS：递归模板

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

注意很多终止条件可以在递归前加判断，有效减少了多一层递归。

BFS：队列

func bfs(grid [][]byte, visited [][]bool, x, y int) {
	queue := make([][]int, 0)
	queue = append(queue, []int{x, y})
	visited[x][y] = true
	for len(queue) != 0 {
		x := queue[0][0]
		y := queue[0][1]
		queue = queue[1:]
		for i := 0; i < 4; i++ {
			nextx := x + direction[i][0]
			nexty := y + direction[i][1]
			if nextx < 0 || nextx >= len(grid) || nexty < 0 || nexty >= len(grid[0]) {
				continue
			}
			if !visited[nextx][nexty] {
				queue = append(queue, []int{nextx, nexty})
				visited[nextx][nexty] = true
			}
		}
	}
}

岛屿数量

双重for循环对每个点进行检查

dfs是采用递归来往下搜索，而bfs是用队列来控制搜索

本质是对每个点都尝试进行检查和搜索，然后搜索后汇聚形成答案。