图论

补充题 23 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 三色染色法，拓扑排序，检测是否有环。 时间复杂度：O(n+m)，其中 n 是 numCourses，m 是 prerequisites 的长度。每个节点至多递归访问一次，每条边至多遍历一次。 空间复杂度：O(n+m)。存储 g 需要 O(n+m) 的空间。 ...

LeetCode 207 https://leetcode.cn/problems/course-schedule/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 三色标记法找环。 对于每个节点 x，都定义三种颜色值： 0：x 尚未被访问到。 1：x 正在被访问，dfs(x) 尚未结束。 2：x 已访问完毕，dfs(x) 已返回。 如果在递归过程中，发现下一个节点在递归栈中（正在访问中），则找到了环。 时间复杂度：O(n+m)，其中 n 是 numCourses，m 是 prerequisites 的长度。每个节点至多递归访问一次，每条边至多遍历一次。 空间复杂度：O(n+m)。存储 g 需要 O(n+m) 的空间。 ...

LeetCode:695 https://leetcode.cn/problems/max-area-of-island/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 网格图 DFS，类似 LeetCode 200 岛屿数量，增加一个当前岛屿面积的计算。 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。 ...

LeetCode 200 https://leetcode.cn/problems/number-of-islands/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是一道图论 DFS 的题目。初始图中的陆地为 1，水为 0。当我们遍历陆地的时候，将遍历过的陆地改为 2，以防止重复访问。 遍历整张图，如果发现 grid[i][j] == 1，说明这是一块没被访问过的岛屿，dfs(i, j)，岛屿数量加一。 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。 ...

本文介绍用三色标记法求拓扑排序。例题：LeetCode 210 课程表 II。 ...

之前介绍了 Dijkstra 单源最短路算法，本文介绍 Floyd 全源最短路算法。例题： LeetCode 1334 阈值距离内邻居最少的城市。 ...

并查集是一种求图的连通分量数量的算法。 ...

本文介绍一种最常用的求单源最短路的算法 Dijkstra。例题：洛谷 P4779 【模板】单源最短路径（标准版）。 ...