算法编程题：图遍历与搜索（5 题）
066 统计二维网格中由上下左右相邻陆地组成的岛屿数量。
难度： 基础
方法签名： char[][] grid
输入约束： grid 为矩形，元素仅为 0 或 1，允许修改输入
示例： [[“1”,“1”,“0”],[“0”,“1”,“0”],[“1”,“0”,“1”]] → 3
目标复杂度： 时间 O(rowscols)，额外空间 O(rowscols)
查看参考答案
解题思路： 扫描每个未访问陆地并用 BFS 淹没其整个连通分量。
不变量： 每次 BFS 结束后，一个岛屿的全部陆地都已标记为水。
public static class AlgCode066Solution
{
public static int Solve(char[][] grid)
{
if (grid.Length == 0) return 0;
int rows = grid.Length, columns = grid[0].Length, islands = 0;
int[][] directions = [[1,0],[-1,0],[0,1],[0,-1]];
for (int row = 0; row < rows; row++)
{
for (int column = 0; column < columns; column++)
{
if (grid[row][column] != '1') continue;
islands++;
var queue = new Queue<(int Row, int Column)>();
queue.Enqueue((row, column));
grid[row][column] = '0';
while (queue.Count > 0)
{
var current = queue.Dequeue();
foreach (int[] direction in directions)
{
int nextRow = current.Row + direction[0];
int nextColumn = current.Column + direction[1];
if (nextRow < 0 || nextRow >= rows ||
nextColumn < 0 || nextColumn >= columns ||
grid[nextRow][nextColumn] != '1') continue;
grid[nextRow][nextColumn] = '0';
queue.Enqueue((nextRow, nextColumn));
}
}
}
}
return islands;
}
}复杂度： 时间 O(rowscols)，队列最坏空间 O(rowscols)。
边界用例： 空网格；全水；全陆地；单行或单列。
面试追问：
- 如果不能修改输入，应使用什么 visited 结构？
067 深拷贝一个无向连通图。
难度： 进阶
方法签名： GraphNode? node
输入约束： 节点值不保证唯一，按引用识别节点
示例： 副本结构与值相同，但不共享任何节点引用
目标复杂度： 时间 O(V+E)，额外空间 O(V)
查看参考答案
解题思路： BFS 建立原节点到副本的映射，并在扫描邻边时连接副本。
不变量： 映射中的每个原节点都有唯一副本，入队前已经创建。
public static class AlgCode067Solution
{
public sealed class GraphNode
{
public int Value;
public List<GraphNode> Neighbors = [];
public GraphNode(int value) => Value = value;
}
public static GraphNode? Solve(GraphNode? node)
{
if (node is null) return null;
var copies = new Dictionary<GraphNode, GraphNode>
{
[node] = new GraphNode(node.Value),
};
var queue = new Queue<GraphNode>();
queue.Enqueue(node);
while (queue.Count > 0)
{
GraphNode current = queue.Dequeue();
foreach (GraphNode neighbor in current.Neighbors)
{
if (!copies.ContainsKey(neighbor))
{
copies[neighbor] = new GraphNode(neighbor.Value);
queue.Enqueue(neighbor);
}
copies[current].Neighbors.Add(copies[neighbor]);
}
}
return copies[node];
}
}复杂度： 时间 O(V+E)，映射和队列空间 O(V)，副本邻边为结果空间。
边界用例： 空图；自环；重复边；节点值重复。
面试追问：
- 递归 DFS 克隆的栈空间边界是什么？
068 返回无权图中起点到终点的最短边数。
难度： 进阶
方法签名： int[][] adjacency, int start, int target
输入约束： 顶点编号为 0..n-1，邻接表只含合法编号
示例： [[1,2],[3],[3],[]], 0, 3 → 2
目标复杂度： 时间 O(V+E)，额外空间 O(V)
查看参考答案
解题思路： BFS 按层扩展，首次发现目标时返回其距离。
不变量： 队列中的距离非递减，每个节点只在首次发现时入队。
public static class AlgCode068Solution
{
public static int Solve(
int[][] adjacency,
int start,
int target)
{
var distance = Enumerable.Repeat(-1, adjacency.Length).ToArray();
var queue = new Queue<int>();
distance[start] = 0;
queue.Enqueue(start);
while (queue.Count > 0)
{
int current = queue.Dequeue();
if (current == target) return distance[current];
foreach (int neighbor in adjacency[current])
{
if (distance[neighbor] >= 0) continue;
distance[neighbor] = distance[current] + 1;
queue.Enqueue(neighbor);
}
}
return -1;
}
}复杂度： 时间 O(V+E)，额外空间 O(V)。
边界用例： 起点等于终点；目标不可达；孤立节点；存在环。
面试追问：
- 边权为非负整数时应改用什么算法？
069 判断给定课程依赖是否允许完成全部课程。
难度： 进阶
方法签名： int courseCount, int[][] prerequisites
输入约束： 每项 [course, prerequisite] 均为合法课程编号
示例： 2, [[1,0]] → true；2, [[1,0],[0,1]] → false
目标复杂度： 时间 O(V+E)，额外空间 O(V+E)
查看参考答案
解题思路： 构建入度和邻接表，用 Kahn 拓扑排序统计已处理课程。
不变量： 队列只包含当前入度为零、可以立即学习的课程。
public static class AlgCode069Solution
{
public static bool Solve(
int courseCount,
int[][] prerequisites)
{
var edges = Enumerable.Range(0, courseCount)
.Select(_ => new List<int>())
.ToArray();
var indegree = new int[courseCount];
foreach (int[] pair in prerequisites)
{
edges[pair[1]].Add(pair[0]);
indegree[pair[0]]++;
}
var queue = new Queue<int>();
for (int course = 0; course < courseCount; course++)
if (indegree[course] == 0) queue.Enqueue(course);
int completed = 0;
while (queue.Count > 0)
{
int current = queue.Dequeue();
completed++;
foreach (int next in edges[current])
if (--indegree[next] == 0) queue.Enqueue(next);
}
return completed == courseCount;
}
}复杂度： 时间 O(V+E)，邻接表、入度和队列空间 O(V+E)。
边界用例： 没有依赖；自环；多个独立分量；重复依赖需按契约去重。
面试追问：
- 如何同时返回一种合法课程顺序？
070 计算多个传播源覆盖全部目标网格所需的最短时间。
难度： 进阶
方法签名： int[][] grid
输入约束： 0 为空、1 为未传播目标、2 为初始传播源，只能上下左右传播
示例： [[2,1,1],[1,1,0],[0,1,1]] → 4
目标复杂度： 时间 O(rowscols)，额外空间 O(rowscols)
查看参考答案
解题思路： 把所有初始源同时入队，按 BFS 层数推进传播。
不变量： 同一层出队的单元具有相同最短传播时间。
public static class AlgCode070Solution
{
public static int Solve(int[][] grid)
{
if (grid.Length == 0) return 0;
int rows = grid.Length, columns = grid[0].Length, remaining = 0;
var queue = new Queue<(int Row, int Column, int Time)>();
for (int row = 0; row < rows; row++)
{
for (int column = 0; column < columns; column++)
{
if (grid[row][column] == 2) queue.Enqueue((row, column, 0));
else if (grid[row][column] == 1) remaining++;
}
}
int[][] directions = [[1,0],[-1,0],[0,1],[0,-1]];
int elapsed = 0;
while (queue.Count > 0)
{
var current = queue.Dequeue();
elapsed = Math.Max(elapsed, current.Time);
foreach (int[] direction in directions)
{
int row = current.Row + direction[0];
int column = current.Column + direction[1];
if (row < 0 || row >= rows ||
column < 0 || column >= columns ||
grid[row][column] != 1) continue;
grid[row][column] = 2;
remaining--;
queue.Enqueue((row, column, current.Time + 1));
}
}
return remaining == 0 ? elapsed : -1;
}
}复杂度： 时间 O(rowscols)，队列最坏空间 O(rowscols)。
边界用例： 没有目标；没有源；目标被障碍隔离；多个源。
面试追问：
- 为什么所有源必须在时间零同时入队？