图
图论题目核心在于深度优先搜索 (DFS)、广度优先搜索 (BFS)、拓扑排序和并查集。
200. 岛屿数量 (Number of Islands)
题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
解题思路
DFS / BFS 沉没法。
- 遍历网格。当遇到 '1' 时，岛屿数量
cnt++。 - 启动 DFS/BFS，将与该 '1' 相连的所有 '1' 全部变为 '0'（即所谓的“沉没岛屿”）。
- 递归四个方向。
Java 代码实现
class Solution {
public int numIslands(char[][] grid) {
int cnt = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
cnt++;
dfs(grid, i, j);
}
}
}
return cnt;
}
private void dfs(char[][] g, int r, int c) {
if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] == '0') return;
g[r][c] = '0';
dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1);
}
}
130. 被围绕的区域 (Surrounded Regions)
题目描述
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
被围绕的区间 不应该包含任何在边界上的 'O'。如果一个 'O' 区域位于边界上，或者与边界上的 'O' 相连，那么该区域内的所有 'O' 都不会被填充为 'X'。如果一个区域不满足上述条件，即该区域完全被 'X' 围绕，则该区域内所有的 'O' 都需要用 'X' 填充。
解题思路
逆向思维：边界出发 DFS。
- 被围绕的区域特指不与边界连通。
- 先从四个边界上的 'O' 出发做 DFS，将相连的 'O' 全部标记为特殊符号（如 'A'）。
- 遍历全盘，将 'A'变回 'O'，将原本剩下的 'O'（被围住的）变回 'X'。
Java 代码实现
class Solution {
public void solve(char[][] board) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) { dfs(board, i, 0); dfs(board, i, n - 1); }
for (int j = 0; j < n; j++) { dfs(board, 0, j); dfs(board, m - 1, j); }
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'A') board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
}
}
}
private void dfs(char[][] b, int r, int c) {
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] != 'O') return;
b[r][c] = 'A';
dfs(b, r + 1, c); dfs(b, r - 1, c); dfs(b, r, c + 1); dfs(b, r, c - 1);
}
}
133. 克隆图 (Clone Graph)
题目描述
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
解题思路
DFS + 哈希表映射。
- 哈希表记录
OldNode -> NewNode。若当前点在表中已存在，直接返回其副本，否则创建副本并递归拷贝邻居。
Java 代码实现
class Solution {
Map<Node, Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
if (map.containsKey(node)) return map.get(node);
Node clone = new Node(node.val);
map.put(node, clone);
for (Node neighbor : node.neighbors) {
clone.neighbors.add(cloneGraph(neighbor));
}
return clone;
}
}
207. 课程表 (Course Schedule)
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
解题思路
拓扑排序 (Kahn 算法)。
- 计算入度。
- 入度为 0 的节点入队。
- 遍历邻居并减少入度，若为 0 则入队。
- 计数比较。
Java 代码实现
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj.get(p[1]).add(p[0]);
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
int cur = q.poll(); count++;
for (int next : adj.get(cur)) {
if (--inDegree[next] == 0) q.offer(next);
}
}
return count == numCourses;
}
}
210. 课程表 II (Course Schedule II)
题目描述
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你返回学完所有课程所安排的学习顺序。如果有多个正确的顺序，只需返回 任意一个 即可。如果不可能完成所有课程，返回 一个空数组 。
解题思路
拓扑排序返回路径。 与 207 题一致，添加数组记录顺序。
Java 代码实现
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj.get(p[1]).add(p[0]);
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) q.offer(i);
int[] res = new int[numCourses];
int index = 0;
while (!q.isEmpty()) {
int cur = q.poll();
res[index++] = cur;
for (int next : adj.get(cur)) {
if (--inDegree[next] == 0) q.offer(next);
}
}
return index == numCourses ? res : new int[0];
}
}
399. 除法求值 (Evaluate Division)
题目描述
给你一个变量对数组 equations 和一个实数值数组 values ，其中 equations[i] = [Ai, Bi] 且 values[i] 代表之间的值。每个 Ai 或 Bi 是一个表示变量的字符串。
另有一个查询数组 queries ，其中 queries[j] = [Cj, Dj] 。你需找出 Cj / Dj = ? 的答案。
返回所有查询的答案。如果存在某个无法确定的答案，则用 -1.0 代替这个答案。如果查询中出现了图网络中未定义的变量，也需用 -1.0 代替。
注意： 输入总是有效的。你可以假设任意查询下，除法分母总是不为 0，且不存在矛盾。
解题思路
带权图 DFS。 建立有向加权图，DFS 寻找路径并累乘权重。
Java 代码实现
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Map<String, Double>> graph = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
String u = equations.get(i).get(0), v = equations.get(i).get(1);
double val = values[i];
graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, val);
graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, 1.0 / val);
}
double[] res = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
res[i] = dfs(queries.get(i).get(0), queries.get(i).get(1), new HashSet<>(), graph);
}
return res;
}
private double dfs(String s, String e, Set<String> visited, Map<String, Map<String, Double>> graph) {
if (!graph.containsKey(s)) return -1.0;
if (s.equals(e)) return 1.0;
visited.add(s);
for (String next : graph.get(s).keySet()) {
if (visited.contains(next)) continue;
double res = dfs(next, e, visited, graph);
if (res != -1.0) return res * graph.get(s).get(next);
}
return -1.0;
}
}