算法入门第七篇：图与搜索：复杂关系网的探索
第七篇：图与搜索：复杂关系网的探索
引言：图的无限可能
朋友们，恭喜你来到了算法学习的又一个高峰——图（Graph）。前几篇我们探索了线性结构和树形结构，它们虽然强大，但不足以描述现实世界中更复杂的**网状（Network）**关系。而图，正是用来描绘和解决这种复杂关系的利器。
图无处不在，渗透在我们生活的方方面面：
-
社交网络：你和朋友之间的关系，朋友和朋友之间的关系，构成了巨大的社交图。如何找到两个人之间的最短关系链？如何发现社群？
-
地图和导航系统：城市、道路、交通流量，它们构成了巨大的交通图。我们每天使用的导航软件，就是基于图算法寻找从起点到终点的最短或最快路径。
-
游戏寻路（Pathfinding）：在游戏中，角色如何在复杂的地图中找到从 A 点到 B 点的路径？这正是图算法 (例如 A* 算法，它基于图的搜索) 的典型应用。
-
计算机网络：互联网、局域网中的设备连接。
-
物流配送、电路设计、推荐系统等等，背后都有图的身影。
理解图的表示、遍历和核心算法，将极大地拓展你解决复杂问题的能力，让你能够驾驭那些看似无序、实则充满内在联系的数据。
图（Graph）
图是由**顶点（Vertex，或称节点 Node）和连接这些顶点的边（Edge）**组成的数据结构。
基本概念
-
顶点（Vertex/Node）：图中的基本元素，表示实体。例如，社交网络中的“人”，地图上的“城市”。
-
边（Edge）：连接两个顶点的线，表示顶点之间的关系。例如，社交网络中的“好友关系”，地图上的“道路”。
-
有向图（Directed Graph / Digraph）：图中的边有方向，表示单向关系。例如，微博的关注关系（你关注某人，但TA不一定关注你）。
-
无向图（Undirected Graph）：图中的边没有方向，表示双向关系。例如，微信的好友关系（A是B的好友，B也一定是A的好友）。
-
带权图（Weighted Graph）：边上带有权值（Weight）的图。权值可以表示距离、成本、时间等。例如，地图上两城市之间的道路长度。
-
连通图（Connected Graph）：在一个无向图中，任意两个顶点之间都存在路径，则称之为连通图。
-
连通分量（Connected Component）：在一个无向图中，一个最大的连通子图。非连通图由多个连通分量组成。
-
度（Degree）：
-
无向图：一个顶点的度是与该顶点相连的边的数量。
-
有向图：
-
入度（In-degree）：指向该顶点的边的数量。
-
出度（Out-degree）：从该顶点指出的边的数量。
-
-
图的表示方法
在计算机中，我们如何存储和表示一个图呢？主要有两种方法：邻接矩阵和邻接表。
1. 邻接矩阵（Adjacency Matrix）
-
概念：
用一个 NtimesN 的二维数组（矩阵）来表示图，其中 N 是图中顶点的数量。
如果顶点 i 和顶点 j 之间有边，则 matrix[i][j] 为 1（或边权值）；否则为 0（或无穷大）。
-
无向图：邻接矩阵是对称的（
matrix[i][j] == matrix[j][i]）。 -
有向图：邻接矩阵可能不对称。
-
-
图示（无向图为例）：
顶点：A, B, C, D (0, 1, 2, 3)
边：(A,B), (A,C), (B,C), (C,D)
A B C D A 0 1 1 0 B 1 0 1 0 C 1 1 0 1 D 0 0 1 0 -
优缺点：
-
优点：
-
判断任意两个顶点之间是否有边非常高效，只需 O(1) 时间查询
matrix[i][j]。 -
方便计算顶点的度（对无向图，一行或一列的和；对有向图，入度为列和，出度为行和）。
-
-
缺点：
-
空间复杂度高：总是需要 O(N2) 的空间，即使图非常稀疏（边很少）。当 N 很大时，会造成内存浪费。
-
查找某个顶点的所有邻居需要遍历一行，时间复杂度为 O(N)。
-
-
-
C# 示例：
C#
// 假设有 N 个顶点 int numVertices = 5; int[,] adjacencyMatrix = new int[numVertices, numVertices]; // 添加边 (0, 1) adjacencyMatrix[0, 1] = 1; // 无向图也需要 adjacencyMatrix[1, 0] = 1; // 添加带权边 (2, 3) 权重为 5 // adjacencyMatrix[2, 3] = 5;
2. 邻接表（Adjacency List）
-
概念：
为图中的每个顶点维护一个列表（或数组），存储与该顶点直接相连的所有邻居顶点。
通常使用**数组（或哈希表）**来存储每个顶点的列表，数组的索引或哈希表的键代表顶点。
-
无向图：如果 (u, v) 是边，则 u 的列表中包含 v，v 的列表中包含 u。
-
有向图：如果 (u, v) 是边，则 u 的列表中包含 v，v 的列表中不包含 u（除非有反向边）。
-
-
图示（与邻接矩阵相同的无向图）：
顶点：A, B, C, D (0, 1, 2, 3)
边：(A,B), (A,C), (B,C), (C,D)
0 (A): [1, 2] 1 (B): [0, 2] 2 (C): [0, 1, 3] 3 (D): [2] -
优缺点：
-
优点：
-
空间复杂度低：只存储实际存在的边，空间复杂度为 O(N+E)，其中 E 是边的数量。对于稀疏图（E 远小于 N2），邻接表比邻接矩阵节省大量空间。
-
查找某个顶点的所有邻居非常高效，只需遍历其对应的列表，时间复杂度为 O(textdegree(V))。
-
-
缺点：
-
判断任意两个顶点之间是否有边，需要遍历其中一个顶点的邻接列表，最坏情况时间复杂度为 O(N)。
-
实现相对复杂一点。
-
-
-
C# 示例：
C#
// 假设有 N 个顶点 int numVertices = 5; // 使用 List<List<int>> 或者 Dictionary<int, List<int>> // 这里使用 List<List<int>>，索引即顶点编号 List<List<int>> adjacencyList = new List<List<int>>(numVertices); for (int i = 0; i < numVertices; i++) { adjacencyList.Add(new List<int>()); } // 添加边 (0, 1) adjacencyList[0].Add(1); adjacencyList[1].Add(0); // 无向图双向添加 // 添加有向边 (2, 3) // adjacencyList[2].Add(3); -
实际应用更广泛：
由于图在实际中大多是稀疏图，且许多图算法（如 BFS、DFS、Dijkstra 等）都需要遍历顶点的所有邻居，因此邻接表是图在实际应用中最常用和高效的表示方法。
图的遍历
图的遍历是指从图中某个顶点出发，系统地访问图中所有可达顶点，且每个顶点只访问一次。图的遍历是许多图算法的基础。主要有两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）。
为了避免重复访问，我们需要一个 visited 集合（或布尔数组）来记录已经访问过的顶点。
1. 深度优先搜索（DFS）
-
原理：
DFS 类似于树的深度优先遍历（前序、中序、后序）。它从一个起始顶点开始，尽可能深地探索每个分支，直到不能再深入为止，然后回溯到上一个未访问的邻居顶点，继续探索。
-
实现方式：
-
递归：最常见和简洁的方式，利用系统调用栈。
-
迭代：手动使用**栈（Stack）**来模拟递归栈。
-
-
图示：
假设图如下（顶点0到5）：
0 – 1
| |
2 – 3 – 4
|
5
从顶点 0 开始 DFS 遍历：
访问 0 -> 访问 1 -> 访问 3 -> 访问 2 (回溯到3，3的邻居2已访问，回溯到1，1的邻居0已访问，回溯到0，0的邻居2已访问) -> 访问 4 -> 访问 5 (回溯…)
一种可能的顺序：0 -> 1 -> 3 -> 2 -> 4 -> 5
-
应用：
-
判断连通性：从一个顶点开始 DFS，如果最终
visited集合包含了所有顶点，则图是连通的（对于无向图）。 -
寻找路径：可以用来判断两个顶点之间是否存在路径。
-
环检测：在有向图或无向图中检测是否存在环。
-
拓扑排序（后面会详细介绍）。
-
-
代码实现（递归）：
C#
public class GraphDFS { private int numVertices; private List<List<int>> adj; // 邻接表 private bool[] visited; public GraphDFS(int v) { numVertices = v; adj = new List<List<int>>(v); for (int i = 0; i < v; i++) { adj.Add(new List<int>()); } visited = new bool[v]; } public void AddEdge(int u, int v) { adj[u].Add(v); adj[v].Add(u); // 如果是无向图 } public void DFS(int startVertex) { Array.Fill(visited, false); // 重置访问状态 Console.Write("DFS Traversal (Recursive): "); DFSUtil(startVertex); Console.WriteLine(); } private void DFSUtil(int v) { visited[v] = true; Console.Write(v + " "); foreach (int neighbor in adj[v]) { if (!visited[neighbor]) { DFSUtil(neighbor); } } } // 迭代实现 DFS public void DFSIterative(int startVertex) { Array.Fill(visited, false); Stack<int> stack = new Stack<int>(); stack.Push(startVertex); visited[startVertex] = true; Console.Write("DFS Traversal (Iterative): "); while (stack.Count > 0) { int v = stack.Pop(); Console.Write(v + " "); // 遍历邻居，将未访问的邻居压入栈 // 为了与递归结果保持一致（或特定顺序），通常倒序遍历邻居，或先压入右边/后边的邻居 // 这里按邻接表的顺序（从左到右）遍历，所以邻居压栈顺序可能影响输出 // 但只要能遍历所有可达节点即可 foreach (int neighbor in adj[v]) { if (!visited[neighbor]) { visited[neighbor] = true; stack.Push(neighbor); } } } Console.WriteLine(); } }
2. 广度优先搜索（BFS）
-
原理：
BFS 类似于树的层序遍历。它从一个起始顶点开始，先访问其所有直接邻居，然后访问这些邻居的邻居（即第二层节点），以此类推，逐层向外扩展。
-
实现方式：
- 手动使用队列（Queue）。
-
图示（与 DFS 相同的图）：
从顶点 0 开始 BFS 遍历：
访问 0
第一层：0 的邻居 (1, 2) 入队
弹出 1 -> 1 的邻居 (0, 3) 入队 (0 已访问)
弹出 2 -> 2 的邻居 (0, 3) 入队 (0 已访问)
弹出 3 -> 3 的邻居 (1, 2, 4, 5) 入队 (1, 2 已访问) -> 4, 5 入队
弹出 4
弹出 5
一种可能的顺序：0 -> 1 -> 2 -> 3 -> 4 -> 5
-
应用：
-
最短路径（无权图）：BFS 可以找到无权图中从起始顶点到所有其他可达顶点的最短路径（按边数计算）。
-
层级遍历：按层访问节点。
-
扩散问题：例如“腐烂的橘子”、“连通分量”等问题，可以模拟扩散过程。
-
-
代码实现：
C#
public class GraphBFS { private int numVertices; private List<List<int>> adj; // 邻接表 public GraphBFS(int v) { numVertices = v; adj = new List<List<int>>(v); for (int i = 0; i < v; i++) { adj.Add(new List<int>()); } } public void AddEdge(int u, int v) { adj[u].Add(v); adj[v].Add(u); // 如果是无向图 } public void BFS(int startVertex) { bool[] visited = new bool[numVertices]; Queue<int> queue = new Queue<int>(); visited[startVertex] = true; queue.Enqueue(startVertex); Console.Write("BFS Traversal: "); while (queue.Count > 0) { int v = queue.Dequeue(); Console.Write(v + " "); foreach (int neighbor in adj[v]) { if (!visited[neighbor]) { visited[neighbor] = true; queue.Enqueue(neighbor); } } } Console.WriteLine(); } }
经典面试题与解法
1. 岛屿数量（Number of Islands）
-
题目描述：
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或垂直方向上相邻的陆地连接形成。你可以假设网格的四个边界都被水包围。
-
解题思路：DFS/BFS 遍历连通分量
这个问题是典型的连通分量问题。每个岛屿就是一个连通分量。我们可以遍历整个网格：
-
当遇到一个
'1'（陆地）时，说明我们发现了一个新的岛屿。岛屿数量加一。 -
然后，从这个
'1'开始，使用 DFS 或 BFS 遍历所有与其相连的陆地，并将它们标记为已访问（例如，改为'0'），以避免重复计数。 -
继续遍历网格，直到所有位置都被访问。
-
-
DFS 实现：
C#
public class Solution { public int NumIslands(char[][] grid) { if (grid == null || grid.Length == 0) { return 0; } int numRows = grid.Length; int numCols = grid[0].Length; int numIslands = 0; for (int r = 0; r < numRows; r++) { for (int c = 0; c < numCols; c++) { if (grid[r][c] == '1') { numIslands++; // 发现新岛屿，从当前陆地开始，淹没所有相连的陆地 SinkIslandDFS(grid, r, c, numRows, numCols); } } } return numIslands; } // DFS 辅助函数，将当前陆地及其所有相连陆地标记为 '0'（即“淹没”） private void SinkIslandDFS(char[][] grid, int r, int c, int numRows, int numCols) { // 越界或遇到水或已访问的陆地 (已改为 '0') if (r < 0 || r >= numRows || c < 0 || c >= numCols || grid[r][c] == '0') { return; } grid[r][c] = '0'; // 标记为已访问（淹没） // 递归向上下左右四个方向扩散 SinkIslandDFS(grid, r + 1, c, numRows, numCols); SinkIslandDFS(grid, r - 1, c, numRows, numCols); SinkIslandDFS(grid, r, c + 1, numRows, numCols); SinkIslandDFS(grid, r, c - 1, numRows, numCols); } } -
BFS 实现：
C#
using System.Collections.Generic; public class Solution { public int NumIslandsBFS(char[][] grid) { if (grid == null || grid.Length == 0) { return 0; } int numRows = grid.Length; int numCols = grid[0].Length; int numIslands = 0; Queue<(int, int)> queue = new Queue<(int, int)>(); // 存储坐标 (row, col) for (int r = 0; r < numRows; r++) { for (int c = 0; c < numCols; c++) { if (grid[r][c] == '1') { numIslands++; grid[r][c] = '0'; // 发现新岛屿，立刻标记为已访问 queue.Enqueue((r, c)); // 将起始点入队 while (queue.Count > 0) { (int currR, int currC) = queue.Dequeue(); // 定义四个方向的偏移量：右、左、下、上 int[] dr = {0, 0, 1, -1}; int[] dc = {1, -1, 0, 0}; for (int i = 0; i < 4; i++) { int nr = currR + dr[i]; int nc = currC + dc[i]; // 检查新坐标是否在网格内，且是未访问的陆地 if (nr >= 0 && nr < numRows && nc >= 0 && nc < numCols && grid[nr][nc] == '1') { grid[nr][nc] = '0'; // 标记为已访问 queue.Enqueue((nr, nc)); // 入队，继续扩散 } } } } } } return numIslands; } } -
复杂度分析：
-
时间复杂度：O(RtimesC)，其中 R 是行数，C 是列数。每个格子最多被访问一次。
-
空间复杂度：O(RtimesC)，最坏情况下（整个网格都是陆地），DFS 的递归栈深度或 BFS 的队列大小可能达到 O(RtimesC)。
-
2. 克隆图（Clone Graph）
-
题目描述：
给你无向连通图中的一个节点的引用。返回该图的深拷贝（即，复制图）。
图中的每个节点都包含一个 val（int 类型）和一个 neighbors 列表（List）。
-
解题思路：DFS/BFS 遍历与哈希表记录已访问节点，处理循环引用
图的克隆问题涉及到深拷贝，关键在于处理循环引用。由于图是连通的，并且节点之间可能相互指向，普通的递归深拷贝会陷入无限循环。我们需要一个机制来记录哪些节点已经被创建并拷贝过。
核心思路：使用哈希表
Dictionary<Node, Node>来存储原始节点到其克隆节点的映射。-
DFS 实现：
-
如果当前节点为
null，直接返回null。 -
如果当前节点已经存在于哈希表中（说明它已经被克隆过），直接返回其克隆节点。
-
创建一个新的克隆节点
cloneNode，其val与原节点相同。 -
将原节点和
cloneNode存入哈希表：map[node] = cloneNode。 -
遍历原节点的每一个邻居 neighbor：
a. 递归地调用克隆函数 CloneGraph(neighbor)，得到邻居的克隆节点。
b. 将这个克隆节点加入 cloneNode 的 neighbors 列表中。
-
返回
cloneNode。
-
-
BFS 实现：
-
如果当前节点为
null，直接返回null。 -
创建一个哈希表
map和一个队列queue。 -
创建起始节点的克隆节点
cloneRoot，并将其存入哈希表：map[node] = cloneRoot。 -
将原起始节点
node加入队列。 -
循环直到队列为空：
a. 从队列中取出当前原节点 currNode。
b. 获取 currNode 对应的克隆节点 currCloneNode (从 map 中获取)。
c. 遍历 currNode 的所有邻居 neighbor：
i. 如果 neighbor 尚未被克隆（不在 map 中）：
-
创建 neighbor 的克隆节点 cloneNeighbor。
-
将 neighbor 和 cloneNeighbor 存入 map。
-
将 neighbor 加入队列。
ii. 将 neighbor 对应的克隆节点（从 map 中获取）添加到 currCloneNode 的 neighbors 列表中。1
-
-
返回
cloneRoot。2
-
-
-
代码实现（DFS）：3
C#
using System.Collections.Generic; // Definition for a Node. public class Node { public int val; public IList<Node> neighbors; public Node() { val = 0; neighbors = new List<Node>(); } public Node(int _val) { val = _val; neighbors = new List<Node>(); } public Node(int _val, List<Node> _neighbors) { val = _val; neighbors = _neighbors; } } public class Solution { // 使用字典来存储原节点到克隆节点的映射，避免重复克隆和处理循环引用 private Dictionary<Node, Node> visitedMap = new Dictionary<Node, Node>(); public Node CloneGraph(Node node) { if (node == null) { return null; } // 如果节点已经被访问并克隆过，直接返回其克隆版本 if (visitedMap.ContainsKey(node)) { return visitedMap[node]; } // 创建新节点（克隆） Node cloneNode = new Node(node.val); // 存储映射关系，表示这个原节点已经被克隆 visitedMap[node] = cloneNode; // 递归克隆邻居节点，并添加到新节点的邻居列表中 foreach (Node neighbor in node.neighbors) { cloneNode.neighbors.Add(CloneGraph(neighbor)); } return cloneNode; } } -
复杂度分析：
-
时间复杂度：O(N+E)，其中 N 是顶点数，E 是边数。每个顶点和每条边只被访问一次。
-
空间复杂度：O(N)，用于存储
visitedMap和递归栈空间（DFS）或队列空间（BFS）。
-
3. 课程表（Course Schedule）
-
题目描述：
你总共有 numCourses 门课需要选，课程编号从 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] 表示选修课程 ai 之前 必须 先修学 bi 。
例如，如果 [0, 1] 表示你必须先修完课程 1 才能修完课程 0 。
如果能完成所有课程，返回 true；否则，返回 false。
-
解题思路：拓扑排序（Topological Sort）与判断有向无环图（DAG）
这个问题是典型的拓扑排序问题。课程和先决条件构成了有向图。如果一个有向图存在环，则无法完成所有课程（例如，A -> B -> C -> A，形成一个死循环）。因此，问题等价于判断图是否为有向无环图（DAG），并找到一个拓扑排序序列。
拓扑排序（Topological Sort）：对一个有向无环图（DAG）的所有顶点进行线性排序，使得对于图中的任意一条有向边
(u, v)，u在排序中都出现在v之前。主要有两种算法实现拓扑排序：
-
Kahn 算法（基于 BFS，入度）：
-
概念：
-
计算每个顶点的入度（有多少条边指向它）。
-
将所有入度为 0 的顶点加入队列。
-
循环直到队列为空：
a. 从队列中取出一个顶点 u，将其加入拓扑排序结果列表。
b. 对于 u 的每个邻居 v，将其入度减 1。
c. 如果 v 的入度变为 0，则将 v 加入队列。
-
如果最终拓扑排序结果列表中的顶点数量等于图中的总顶点数量，则说明图是 DAG，存在拓扑排序；否则，图存在环。
-
-
判断有向无环图（DAG）：Kahn 算法自然地提供了判断 DAG 的方法。如果最终排序的顶点数量不等于总顶点数量，则图中存在环。
-
-
DFS 算法（基于回溯）：
-
概念：
利用 DFS 遍历图。在 DFS 过程中，需要维护三种状态来检测环：
-
visited：已访问过且已处理完的节点（已加入拓扑序列）。 -
visiting：正在递归栈中的节点（正在访问）。 -
未访问：尚未访问的节点。
如果在 DFS 过程中，遇到一个 visiting 状态的节点，说明存在环。
当一个节点的 DFS 遍历完成后（所有邻居都被访问或处理完），将其加入拓扑序列的头部（因为是逆后序）。
-
-
-
-
Kahn 算法 (BFS) 实现：
C#
using System.Collections.Generic; public class Solution { public bool CanFinish(int numCourses, int[][] prerequisites) { // 1. 构建邻接表和计算入度数组 List<List<int>> adj = new List<List<int>>(numCourses); for (int i = 0; i < numCourses; i++) { adj.Add(new List<int>()); } int[] inDegree = new int[numCourses]; // 记录每个课程的入度 foreach (int[] prerequisite in prerequisites) { int course = prerequisite[0]; // 0 依赖于 1 int preCourse = prerequisite[1]; adj[preCourse].Add(course); // preCourse -> course inDegree[course]++; } // 2. 将所有入度为 0 的课程加入队列 Queue<int> queue = new Queue<int>(); for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) { queue.Enqueue(i); } } int coursesTaken = 0; // 记录已完成的课程数量 // 3. BFS 遍历 while (queue.Count > 0) { int course = queue.Dequeue(); coursesTaken++; // 遍历当前课程的后续课程 foreach (int nextCourse in adj[course]) { inDegree[nextCourse]--; // 移除对 nextCourse 的依赖 if (inDegree[nextCourse] == 0) { queue.Enqueue(nextCourse); // 如果 nextCourse 入度变为 0，加入队列 } } } // 4. 判断是否所有课程都能完成 return coursesTaken == numCourses; } } -
复杂度分析：
-
时间复杂度：O(N+E)，其中 N 是课程数量（顶点数），E 是先决条件数量（边数）。构建图和遍历图都只访问一次顶点和边。
-
空间复杂度：O(N+E)，用于存储邻接表和入度数组、队列。
-
4. 腐烂的橘子（Rotting Oranges）
-
题目描述：
在一个 mtimesn 的网格中，每个单元格可以是：
-
0代表空单元格。 -
1代表新鲜橘子。 -
2 代表腐烂的橘子。
每分钟，任何与腐烂橘子相邻（上、下、左、右）的新鲜橘子都会腐烂。
返回所有橘子腐烂所需的最少分钟数。如果不可能让所有新鲜橘子都腐烂，则返回 -1。
-
-
解题思路：多源 BFS 问题
这道题是经典的多源 BFS 问题。它类似于水波扩散，从多个起始点（所有腐烂的橘子）同时开始扩散。BFS 最适合解决这种最短路径（或最少步数）的问题。
步骤：
-
初始化：
-
将所有初始腐烂的橘子（
2）加入 BFS 队列。 -
统计新鲜橘子（
1）的数量。 -
记录经过的分钟数
minutes。
-
-
BFS 过程：
-
每一轮 BFS 循环代表一分钟的流逝。
-
在每一轮开始时，记录当前队列中的橘子数量
currentLevelSize。这些橘子是上一个时间点腐烂的，它们将导致它们周围的新鲜橘子在本轮腐烂。 -
循环 currentLevelSize 次：
a. 从队列中取出一个腐烂橘子。
b. 检查其四个方向的邻居：
i. 如果邻居是新鲜橘子 (1)：将其变为腐烂 (2)，新鲜橘子数量减 1，并将新腐烂的橘子加入队列。
-
如果当前轮有新的橘子腐烂，
minutes加 1。
-
-
判断结果：
-
BFS 结束后，如果新鲜橘子数量为 0，则返回
minutes。 -
否则，表示有新鲜橘子无法腐烂，返回
-1。
-
-
-
代码实现：
C#
using System.Collections.Generic; public class Solution { public int OrangesRotting(int[][] grid) { if (grid == null || grid.Length == 0) { return 0; } int numRows = grid.Length; int numCols = grid[0].Length; Queue<(int, int)> queue = new Queue<(int, int)>(); int freshOranges = 0; // 统计新鲜橘子数量 // 1. 初始化队列，将所有初始腐烂橘子入队，并统计新鲜橘子 for (int r = 0; r < numRows; r++) { for (int c = 0; c < numCols; c++) { if (grid[r][c] == 2) { queue.Enqueue((r, c)); } else if (grid[r][c] == 1) { freshOranges++; } } } // 如果没有新鲜橘子，直接返回 0 分钟 if (freshOranges == 0) { return 0; } int minutes = 0; // 定义四个方向的偏移量：右、左、下、上 int[] dr = {0, 0, 1, -1}; int[] dc = {1, -1, 0, 0}; // 2. BFS 过程 while (queue.Count > 0) { int levelSize = queue.Count; // 当前轮次（当前分钟）需要处理的腐烂橘子数量 bool didRotAny = false; // 标记本轮是否有新鲜橘子腐烂 for (int i = 0; i < levelSize; i++) { (int currR, int currC) = queue.Dequeue(); for (int j = 0; j < 4; j++) { int nr = currR + dr[j]; int nc = currC + dc[j]; // 检查新坐标是否在网格内，且是新鲜橘子 if (nr >= 0 && nr < numRows && nc >= 0 && nc < numCols && grid[nr][nc] == 1) { grid[nr][nc] = 2; // 标记为腐烂 freshOranges--; // 新鲜橘子数量减一 queue.Enqueue((nr, nc)); // 新腐烂的橘子入队 didRotAny = true; // 本轮有橘子腐烂 } } } // 如果本轮有橘子腐烂，分钟数增加 if (didRotAny) { minutes++; } else { // 如果本轮没有橘子腐烂，但队列里还有橘子，说明这些橘子都是已经腐烂过的， // 并且它们周围已经没有新鲜橘子可腐烂了，可以提前结束循环 // (其实可以不加这个，因为 freshOranges==0 会提前判断) } } // 3. 判断结果 return freshOranges == 0 ? minutes : -1; } } -
复杂度分析：
-
时间复杂度：O(RtimesC)。每个单元格最多入队和出队一次。
-
空间复杂度：O(RtimesC)。最坏情况下所有橘子都在队列中。
-
补充算法（概念性介绍，知晓即可）
这些是图领域更高级和复杂的算法，在面试中通常只会要求你了解其概念、用途和复杂度。
1. 并查集（Union-Find Set）
-
概念：
一种用于处理一些不相交集合（Disjoint Sets）的抽象数据类型。它支持两种主要操作：
-
并（Union）：合并两个集合。
-
查（Find）：查找元素所属的集合的代表元素（通常是根节点），可以判断两个元素是否在同一个集合中。
并查集通常采用树形结构实现，并通过**路径压缩（Path Compression）和按秩/大小合并（Union by Rank/Size）**优化，使其操作接近 O(alpha(N))（阿克曼函数的反函数，非常接近常数时间）。
-
-
应用：
-
连通分量：判断图中两个顶点是否连通，或者统计图中有多少个连通分量。
-
判断图是否有环：在构建图时，如果添加一条边
(u, v)发现u和v已经在同一个集合中（即它们已连通），则说明添加这条边会形成环。这是Kruskal 算法（最小生成树算法之一）的基础。 -
网络连接、好友关系、游戏中的联盟系统等。
-
2. 最短路径算法
-
Dijkstra 算法（概念）：
-
用途：解决单源最短路径问题，即从图中一个指定源点到所有其他可达顶点的最短路径。
-
限制：边的权值必须是非负数。
-
思想：使用贪心策略，每次从“未确定最短路径”的顶点中选择距离源点最近的那个顶点，并更新其邻居的距离。通常结合优先队列（或小根堆）实现。
-
时间复杂度：O(ElogN) 或 O(E+NlogN)（使用优先队列）。
-
-
Floyd-Warshall 算法（概念）：
-
用途：解决所有顶点对之间的最短路径问题，即计算图中任意两个顶点之间的最短路径。
-
限制：可以处理负权边，但不能处理负权环（否则最短路径没有定义）。
-
思想：动态规划。通过中间顶点
k来逐步更新任意两点i和j之间的最短路径。 -
时间复杂度：O(N3)。
-
3. 最小生成树（MST）
-
概念：
对于一个带权无向连通图，最小生成树是它的一个子图，它包含了图中所有的顶点，并且只包含足够形成一棵树的边（即 N−1 条边），使得这些边的权值之和最小。
-
Prim 算法（概念）：
-
思想：从一个起始顶点开始，逐步将距离当前生成树最近的边加入树中，直到包含所有顶点。类似 Dijkstra 算法，也常结合优先队列。
-
时间复杂度：O(ElogN) 或 O(E+NlogN)。
-
-
Kruskal 算法（概念）：
-
思想：将所有边按权值从小到大排序，然后依次遍历边。如果添加当前边不会形成环（使用并查集判断），则将其加入最小生成树。
-
时间复杂度：O(ElogE) 或 O(ElogN)（排序和并查集操作）。
-
总结与练习
本篇我们深入探索了图这一强大的非线性数据结构，它能够描述现实世界中各种复杂的网状关系。我们学习了图的基本概念、两种主要表示方法（邻接矩阵和邻接表）及其优缺点。
我们重点掌握了图的两种核心遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS），并理解了它们在不同场景下的应用。通过岛屿数量、克隆图、课程表和腐烂橘子这四个经典面试题的解析，你已经能够将这些遍历算法活学活用。
最后，我们概念性地介绍了更高级的图算法，如拓扑排序、并查集、最短路径算法（Dijkstra、Floyd-Warshall）和最小生成树算法（Prim、Kruskal）。这些算法是图论的精髓，掌握它们的思想将让你在复杂问题面前游刃有余。
本篇核心知识点回顾：
-
图的基本概念：顶点、边、有向/无向、带权、连通性、度。
-
图的表示：邻接矩阵 (O(N2) 空间，判断边 O(1)) 和 邻接表 (O(N+E) 空间，实际更常用)。
-
图的遍历：
-
DFS：用栈（或递归）实现，擅长深度探索，如找路径、环检测。
-
BFS：用队列实现，擅长层级探索，如无权最短路径、扩散问题。
-
-
经典面试题：
-
岛屿数量：DFS/BFS 连通分量。
-
克隆图：DFS/BFS + 哈希表处理循环引用。
-
课程表：拓扑排序（Kahn 算法/DFS 算法），判断 DAG。
-
腐烂的橘子：多源 BFS。
-
-
补充算法：并查集、Dijkstra、Floyd-Warshall、Prim、Kruskal（理解概念和用途）。
课后练习（推荐力扣 LeetCode 题目）：
-
岛屿数量 (Number of Islands)：LeetCode 200。
-
矩阵中的连通分量 (Max Area of Island)：LeetCode 695（和岛屿数量类似）。
-
克隆图 (Clone Graph)：LeetCode 133。
-
课程表 (Course Schedule)：LeetCode 207。
-
课程表 II (Course Schedule II)：LeetCode 210（要求返回拓扑排序结果）。
-
腐烂的橘子 (Rotting Oranges)：LeetCode 994。
-
钥匙和房间 (Keys and Rooms)：LeetCode 841（简单图遍历）。
-
判断二分图 (Is Graph Bipartite?)：LeetCode 785（BFS/DFS 染色问题）。
-
被围绕的区域 (Surrounded Regions)：LeetCode 130（DFS/BFS 边界连通性问题）。
图是计算机科学中最复杂也最迷人的领域之一。大量的实际问题都可以抽象成图论问题并用相应的算法解决。通过本篇的学习和练习，你将对图的结构和算法有更深的理解，为解决更复杂的工程问题打下坚实基础。
下一篇，我们将进入算法设计的高级技巧——动态规划，学习如何化繁为简，解决那些看似无从下手的问题！你准备好了吗？
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
22
0- 0
已为社区贡献2条内容
所有评论(0)