两道常考图算法题-每次做都不会

200. 岛屿数量 - 力扣（LeetCode）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	var dfs func(x, y int)
	ans := 0

	dfs = func(x, y int) {
		if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != '1' {
			return
		}
		grid[x][y] = 2

		dfs(x, y+1)
		dfs(x, y-1)
		dfs(x+1, y)
		dfs(x-1, y)
	}

	for i, row := range grid {
		for j, c := range row {
			if c == '1' {
				dfs(i, j)
				ans++
			}
		}
	}

	return ans
}

该题考查的是图的 DFS 算法，这题也算是典型题了，有不少类似的题都是一个套路。这类题属于二维网格的连通性问题，可以套用下面的框架：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 主函数
func solve(grid):
    // 1. 初始化
    count = 0
    rows = len(grid)
    cols = len(grid[0])

    // 2. 双层循环遍历网格 (雷达扫描)
    for r from 0 to rows-1:
        for c from 0 to cols-1:
            // 3. 寻找触发点 (发现新大陆)
            if grid[r][c] is an unvisited part of a component (e.g., '1'):
                // 4. 计数器加一
                count++
                // 5. 启动搜索，淹没/标记所有相连部分
                explore(grid, r, c) // 可以是 DFS 或 BFS

    return count

// 搜索函数 (可以是 DFS 或 BFS)
func explore(grid, r, c):
    // 实现淹没/标记的逻辑

不要去逐行背代码，而是记住这个模型：

外层循环：固定模式，for r { for c { ... } }，这是为了确保不漏掉任何一个格子。
触发条件：if grid[r][c] == '1'，这是开始一次新搜索的信号。
核心搜索 dfs：记住 dfs 函数的三个核心部分：
- “退路”：先写终止条件，防止跑出界或者重复跑。
- “标记”：紧接着，把脚下的路标记为已走过。
- “前进”：最后，向四个方向迈出下一步（递归调用）。

当下次再遇到这道题，或者类似的题目（如“最大岛屿面积”、“被围绕的区域”等），就可以直接在脑海里构建这个框架，然后往里面填空。

207. 课程表 - 力扣（LeetCode）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func canFinish(numCourses int, prerequisites [][]int) bool {
	dependencies := make([][]int, numCourses)
	inDegree := make([]int, numCourses)

	for _, d := range prerequisites {
		a, b := d[0], d[1]
		dependencies[b] = append(dependencies[b], a)
		inDegree[a]++
	}

	learned := 0
	queue := make([]int, 0)
	for i, degree := range inDegree {
		if degree == 0 {
			queue = append(queue, i)
		}
	}

	for len(queue) > 0 {
		curCourse := queue[0]
		queue = queue[1:]
		learned++

		for _, afterCourse := range dependencies[curCourse] {
			inDegree[afterCourse]--
			if inDegree[afterCourse] == 0 {
				queue = append(queue, afterCourse)
			}
		}
	}
	return learned == numCourses
}

该题考查的是有向图的拓扑排序和环检测，上面的代码就是基于 BFS 的拓扑排序。

想象一下，所有课程的依赖关系就像一个洋葱。

最外层的洋葱皮：这些是没有前置课程的课（比如 “大学英语 I”, “微积分 I”）。在图论里，这些节点的入度 (In-degree) 为 0。它们是你可以最先开始上的课。
剥掉一层：你把这些入度为 0 的课程“上完”（从图中“拿掉”）。
露出新的一层：当你上完了 “微积分 I”，那么 “微积分 II” 的一个前置条件就满足了。如果 “微积分 II” 没有其他前置课程，那么它现在就变成了新的“洋葱皮”（它的入度从 1 变成了 0）。
不断重复：你不断地重复这个过程——找到所有入度为 0 的课，“上完”它们，然后更新它们的后续课程的入度。
结局：
- 成功剥完：如果你能通过这个方法把所有的课程都“上完”，说明课程安排是合理的，没有循环依赖。
- 剩下葱心：如果在某个时刻，你找不到任何入度为 0 的课程了，但还有课没上，这说明剩下的课程形成了一个“死结”，也就是环 (Cycle)。例如：A 依赖 B，B 依赖 C，C 又依赖 A。它们谁也无法成为那个入度为 0 的起点，最后就会剩下。

这个“剥洋葱”的过程，用代码实现出来就是 Kahn 算法。它的框架非常固定：

第一步：建图和统计入度
- 创建一个邻接表 (dependencies in your code)，用来表示课程的指向关系。dependencies[b] = [a] 意味着有一条从 b 到 a 的有向边 (b -> a)。
- 创建一个入度数组 (inDegree in your code)，统计每门课有多少个前置课程。
第二步：找到所有起点
- 创建一个队列 (Queue)。
- 遍历一遍入度数组，把所有入度为 0 的课程（最外层的洋葱皮）放入队列。
第三步：循环处理 (BFS)
- 当队列不为空时，不断循环：
  - 从队列里取出一门课 curCourse（相当于“剥掉”一层）。
  - 用一个计数器 learned 记录“上完”的课程数。
  - 遍历 curCourse 的所有后继课程 afterCourse（即 dependencies[curCourse]）。
  - 对于每一个 afterCourse，将其入度减 1（因为 curCourse 这个前置条件已经满足了）。
  - 关键判断：如果 afterCourse 的入度减到 0 了，说明它已经变成了新的“洋葱皮”，可以上了。于是，将它放入队列。
第四步：验证结果
- 循环结束后，比较“上完”的课程总数 learned 和总课程数 numCourses。
- 如果 learned == numCourses，说明所有课程都被剥掉了，无环，可以完成。
- 否则，说明有环，无法完成。

对于这类拓扑排序问题，记住**“剥洋葱”这个比喻。然后记住实现它的三要素**：

邻接表 (Adjacency List)：表示“谁指向谁”。
入度数组 (In-degree Array)：找到起点和后续的新起点。
队列 (Queue)：存放所有当前可以上的课 (入度为0的课)。

200. 岛屿数量 - 力扣（LeetCode）#

207. 课程表 - 力扣（LeetCode）#

200. 岛屿数量 - 力扣（LeetCode）

207. 课程表 - 力扣（LeetCode）