leetcode-hot-100 (图论）

1. 岛屿数量

题目链接：岛屿数量
题目描述：给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

解答

方法一：深度优先

可以将二维网格看成一个无向图，竖直或水平相邻的 $1$ 之间有边相连（利用图论知识）

为求出岛屿的数量，扫描整个二维网格。如果一个位置为 $1$，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 $1$ 都会被重新标记为 $0$（因为这是属于一个岛屿的）。

最终岛屿的数量就是进行深度优先搜索的次数。(思路比较简单，代码编写也不是很难）

class Solution {private: void dfs(vector<vector<char>>& grid, int r, int c) { int nr = grid.size(); int nc = grid[0].size(); grid[r][c] = \'0\'; if (r - 1 >= 0 && grid[r - 1][c] == \'1\') // 向左探测 dfs(grid, r - 1, c); if (r + 1 < nr && grid[r + 1][c] == \'1\') // 向右探测 dfs(grid, r + 1, c); if (c - 1 >= 0 && grid[r][c - 1] == \'1\') // 向上探测 dfs(grid, r, c - 1); if (c + 1 < nc && grid[r][c + 1] == \'1\') // 向下探测 dfs(grid, r, c + 1); }public: int numIslands(vector<vector<char>>& grid) { int nr = grid.size(); // 记录网格的行数 if (!nr) return 0; int nc = grid[0].size(); // 记录网格的列数 int count_num_islands = 0; // 记录岛屿的数量 for (int row = 0; row < nr; row++) { for (int col = 0; col < nc; col++) { if (grid[row][col] == \'1\') {  count_num_islands++;  dfs(grid, row, col); // 深度优先，将同一个岛屿的1置成0 } } } return count_num_islands; // 返回最终岛屿数量的结果 }};

方法二：广度优先

思想也是类似于深度优先，为了求出岛屿的数量，扫描整个二维网格。如果一个位置为 $1$，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 $1$ 都会被重新标记为 $0$。直到队列为空（这个地方和深度优先类似，深度优先也是搜索到这个岛屿所涉及到的全部位置置成 $0$ ,才进行下一个岛屿的搜索），搜索结束。

class Solution {public: int numIslands(vector<vector<char>>& grid) { int nr = grid.size(); // 记录网格的行数 if (!nr) return 0; int nc = grid[0].size(); // 记录网格的列数 int count_num_island = 0; // 记录岛屿的数量 for (int row = 0; row < nr; row++) { for (int col = 0; col < nc; col++) { if (grid[row][col] == \'1\') {  ++count_num_island;  grid[row][col] = \'0\'; // 对应网格位置数字置成 0  queue<pair<int, int>> neighbors; // 创建队列  neighbors.push({row, col}); // 当前网格的位置入队列  while ( !neighbors .empty()) { // 也是类似于深度优先的思路，将该岛屿涉及到的位置全部置成0 auto rc = neighbors.front(); // 记录队列的第一个元素 neighbors.pop();  // 弹出队列的第一个元素 int r = rc.first, c = rc.second; // 双元素队列的相关操作 if (r - 1 >= 0 && grid[r - 1][c] == \'1\') { neighbors.push({r - 1, c}); grid[r - 1][c] = \'0\'; } if (r + 1 < nr && grid[r + 1][c] == \'1\') { neighbors.push({r + 1, c}); grid[r + 1][c] = \'0\'; } if (c - 1 >= 0 && grid[r][c - 1] == \'1\') { neighbors.push({r, c - 1}); grid[r][c - 1] = \'0\'; } if (c + 1 < nc && grid[r][c + 1] == \'1\') { neighbors.push({r, c + 1}); grid[r][c + 1] = \'0\'; }  } } } } return count_num_island; }};

又或者写成下面的形式：

class Solution {public: int numIslands(vector<vector<char>>& grid) { if (grid.empty() || grid[0].empty()) return 0; int nr = grid.size(); int nc = grid[0].size(); vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int count_num_island = 0; for (int row = 0; row < nr; row++) { for (int col = 0; col < nc; col++) { if (grid[row][col] == \'1\') {  ++count_num_island;  grid[row][col] = \'0\'; // 标记已访问  queue<pair<int, int>> neighbors;  neighbors.push({row, col});  while (!neighbors.empty()) { auto rc = neighbors.front(); neighbors.pop(); int r = rc.first; int c = rc.second; for (auto& dir : directions) { int new_r = r + dir.first; int new_c = c + dir.second; if (new_r >= 0 && new_r < nr && new_c >= 0 && new_c < nc && grid[new_r][new_c] == \'1\') { neighbors.push({new_r, new_c}); grid[new_r][new_c] = \'0\'; } }  } } } } return count_num_island; }};

方法三：并查集

有关于并查集的相关介绍详见：并查集
凡是涉及到元素的分组管理问题，都可以考虑使用并查集进行维护。 而该题可以将不同的岛屿看成不同的组，然后对每个位置进行并查集判断是否属于某一个组即可。

思路如下：
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 $1$，则将其与相邻四个方向上的 $1$ 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。

#include #include  // 用于 swapusing namespace std;// 并查集（Union-Find）类，用于高效管理连通分量class UnionFind {private: vector<int> parent; // parent[i] 表示节点 i 的父节点 vector<int> rank; // rank[i] 表示以 i 为根的树的“秩”（近似高度），用于优化合并操作 int count; // 当前连通分量（岛屿）的数量public: // 查找操作：找到节点 i 所在集合的根节点，并进行路径压缩 // 路径压缩：将查找路径上的所有节点直接连接到根节点，加快后续查找 int find(int i) { // 如果 parent[i] == i，说明 i 是根节点，直接返回 // 否则递归查找父节点，并将 parent[i] 更新为根节点（路径压缩） return parent[i] == i ? i : (parent[i] = find(parent[i])); // 上述三元运算符表达式等价于下面的代码 // if (i == parent[i]) { // return i; // } else { // parent[i] = find(parent[i]); // return parent[i]; // } } // 合并操作：将包含 x 和 y 的两个集合合并为一个 void unite(int x, int y) { int rootx = find(x); // 找到 x 所在集合的根 int rooty = find(y); // 找到 y 所在集合的根 // 如果根相同，说明已在同一集合，无需合并 if (rootx != rooty) { // 按秩合并：将秩较小的树合并到秩较大的树下，以保持树的平衡 if (rank[rootx] < rank[rooty]) { swap(rootx, rooty); // 保证 rootx 的秩 >= rooty 的秩 } parent[rooty] = rootx; // 将 rooty 的根指向 rootx // 如果两棵树的秩相等，合并后根节点的秩加 1 if (rank[rootx] == rank[rooty]) { rank[rootx] ++; } // 成功合并两个不同集合，连通分量数量减一 --count; } } // 获取当前连通分量的数量（即岛屿数量） int getCount() const { return count; } // 构造函数：初始化并查集 // grid 是输入的二维网格，\'1\' 表示陆地，\'0\' 表示水 UnionFind(vector<vector<char>>& grid) { count = 0; // 初始化连通分量数量为 0 int m = grid.size(); int n = grid[0].size(); // 遍历整个网格，初始化 parent 和 rank 数组 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == \'1\') {  // 如果是陆地，初始化其父节点为自身（表示独立的一个连通分量）  parent.push_back(i * n + j);  count++; // 每发现一个 \'1\'，连通分量数量加一 } else {  // 如果是水，用 -1 标记，表示无效节点  parent.push_back(-1); } // 初始化每个节点的秩为 0 rank.push_back(0); } } }};// Solution 类：解决“岛屿数量”问题class Solution {public: // 主函数：计算二维网格中岛屿的数量 // 岛屿由相邻的陆地（\'1\'）连接而成，相邻指上下左右四个方向 int numIslands(vector<vector<char>>& grid) { int nr = grid.size();  // 行数 if (!nr) return 0;  // 网格为空，返回 0 int nc = grid[0].size(); // 列数 // 创建并查集对象，自动初始化所有陆地节点为独立连通分量 UnionFind uf(grid); // 遍历整个网格，对每个陆地节点，尝试与相邻的陆地节点合并 for (int r = 0; r < nr; r++) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == \'1\') {  // 将当前陆地置为 \'0\'，防止重复访问（虽然并查集已处理，但此处是习惯性操作）  grid[r][c] = \'0\';  // 检查上方是否有陆地，如果有则合并  if (r - 1 >= 0 && grid[r - 1][c] == \'1\') { uf.unite(r * nc + c, (r - 1) * nc + c);  }  // 检查下方是否有陆地，如果有则合并  if (r + 1 < nr && grid[r + 1][c] == \'1\') { uf.unite(r * nc + c, (r + 1) * nc + c);  }  // 检查左方是否有陆地，如果有则合并  if (c - 1 >= 0 && grid[r][c - 1] == \'1\') { uf.unite(r * nc + c, r * nc + c - 1);  }  // 检查右方是否有陆地，如果有则合并  if (c + 1 < nc && grid[r][c + 1] == \'1\') { uf.unite(r * nc + c, r * nc + c + 1);  } } } } // 返回最终的连通分量数量，即岛屿数量 return uf.getCount(); }};

不写 UnionFind 类的代码：

class Solution {private: vector<int> parent; // 并查集的父节点数组 vector<int> rank; // 用于按秩合并优化 int count; // 当前连通分量（岛屿）的数量 // 查找 + 路径压缩 int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); } // 合并两个集合（按秩合并） void unite(int x, int y) { int rootx = find(x); int rooty = find(y); if (rootx == rooty) return; if (rank[rootx] < rank[rooty]) { swap(rootx, rooty); } parent[rooty] = rootx; if (rank[rootx] == rank[rooty]) { rank[rootx]++; } --count; }public: int numIslands(vector<vector<char>>& grid) { int nr = grid.size(); if (nr == 0) return 0; int nc = grid[0].size(); // 初始化并查集相关数据结构 parent.clear(); rank.clear(); count = 0; // 映射二维坐标到一维：(r, c) -> r * nc + c int total = nr * nc; parent.resize(total); rank.resize(total, 0); // 初始化 rank 为 0 // 遍历网格，初始化 parent 和 count for (int i = 0; i < nr; ++i) { for (int j = 0; j < nc; ++j) { if (grid[i][j] == \'1\') {  parent[i * nc + j] = i * nc + j; // 自己是自己的父节点  count++; // 每个陆地初始为一个连通分量 } else {  parent[i * nc + j] = -1; // 水标记为 -1，表示无效 } } } // 遍历每个格子，与上下左右的陆地合并 for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] != \'1\')  continue; int idx = r * nc + c; // 检查四个方向的邻居 // 上 if (r > 0 && grid[r - 1][c] == \'1\') {  unite(idx, (r - 1) * nc + c); } // 下 if (r < nr - 1 && grid[r + 1][c] == \'1\') {  unite(idx, (r + 1) * nc + c); } // 左 if (c > 0 && grid[r][c - 1] == \'1\') {  unite(idx, r * nc + (c - 1)); } // 右 if (c < nc - 1 && grid[r][c + 1] == \'1\') {  unite(idx, r * nc + (c + 1)); } } } return count; }};

2. 腐烂的橘子

题目链接：腐烂的橘子
题目描述：在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

解答

class Solution {public: int orangesRotting(vector<vector<int>>& grid) { queue<pair<int, int>> q; int dirctions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个方向 int row = grid.size();  // 网格行数 int col = grid[0].size();  // 网格列数 int cnt = 0; // 记录新鲜橘子的数量 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == 2) {  q.push({i, j}); } else if (grid[i][j] == 1) {  cnt++; } } } // 没有腐烂橘子，有新鲜橘子，直接返回 -1 即可 if (q.empty() && cnt) { return -1; } int ans = 0; // 传播的最小分钟数 while (!q.empty()) { int t = q.size(); // 遍历同一时间感染的橘子 for (int k = 0; k < t; k++) { pair<int, int> p = q.front(); q.pop(); for (auto direction : dirctions) {  int x = p.first + direction[0];  int y = p.second + direction[1];  if (x >= 0 && y >= 0 && x < row && y < col && grid[x][y] == 1) { grid[x][y] = 2; // 新鲜橘子变腐烂 q.push({x, y}); cnt--; // 新鲜橘子减少  } } } if (!q.empty()) // 如果当前轮有新感染的橘子，时间加一 ans++; } if (cnt) // 如果到此处还有没被感染的橘子，直接返回 -1 即可。 return -1; return ans; // 最后没有新鲜橘子了，返回传播的最小分钟数 }};

3. 课程表

题目链接：课程表
题目描述：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

解答

方法一： 拓扑排序（BFS + 邻接表）

这道题学过数据结构的就会发现，这是很经典的图论中的拓扑排序问题。甚至我上课的时候老师也是举的课程学习这个例子。代码如下：

class Solution {public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<int> in_degree(numCourses, 0); vector<vector<int>> graph(numCourses); // 建图 + 计算入度 for (auto& pre : prerequisites) { int course = pre[0]; int prerequisite = pre[1]; graph[prerequisite].push_back(course); in_degree[course]++; } // 找出所有入度为 0 的节点加入队列 queue<int> q; for (int i = 0; i < numCourses; i++) { if (in_degree[i] == 0) q.push(i); } int visited = 0; // 记录能访问的节点数 while (!q.empty()) { int node = q.front(); q.pop(); visited++; // 遍历所有由 node 指向的课程 for (int neighbor : graph[node]) { in_degree[neighbor]--; if (in_degree[neighbor] == 0) {  q.push(neighbor); } } } return visited == numCourses; }};

当然，除了使用邻接表之外，还可以使用邻接矩阵，但是我们老师讲过，在图结构中，尤其是在稀疏图（边数远小于节点数的平方），邻接矩阵比邻接表更高效。

方法二：拓扑排序（DFS + 邻接表）判断是否有环

定义三个状态：

• 0 : 代表未访问
• 1 : 代表正在访问（在当前 DFS 路径中）
• 2 : 代表已访问，且无环

class Solution {private: vector<vector<int>> graph; vector<int> visited; bool dfs(int node) { if (visited[node] == 1) return false; if (visited[node] == 2) return true; visited[node] = 1; for (int neighbor : graph[node]) { if (!dfs(neighbor)) return false; } visited[node] = 2; return true; }public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { graph.resize(numCourses); visited.assign(numCourses, 0); for (auto& pre : prerequisites) { graph[pre[1]].push_back(pre[0]); } for (int i = 0; i < numCourses; i++) { if (!dfs(i)) return false; } return true; }};

4. 实现 Trie (前缀树)

题目链接：实现 Trie (前缀树)
题目描述：Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

解答

// 定义一个名为 Trie 的类，用于实现前缀树（字典树）数据结构class Trie {private: // 标记当前节点是否为一个完整单词的结尾 // 例如，如果插入了 \"apple\"，那么代表 \'e\' 的节点的 isEnd 将为 true bool isEnd; // 指针数组，用于指向当前节点的 26 个可能的子节点（对应 a-z 26 个小写字母） // next[i] 表示从当前节点出发，通过字母 (\'a\' + i) 能到达的子节点 // 如果 next[i] 为 NULL，表示没有以该字母为边的子节点 Trie* next[26];public: // 构造函数：初始化一个新的 Trie 节点 Trie() { isEnd = false; // 默认新节点不是任何单词的结尾 // 将 next 数组的所有指针初始化为 NULL（使用 memset 将内存块清零） // 这样可以确保所有子节点初始都不存在 memset(next, 0, sizeof(next)); } // 向 Trie 中插入一个单词 void insert(string word) { Trie* node = this; // 从根节点开始 // 遍历单词中的每一个字符 for (char c : word) { // 计算当前字符 c 对应的索引（\'a\' -> 0, \'b\' -> 1, ..., \'z\' -> 25） int index = c - \'a\'; // 如果当前节点没有指向字符 c 的子节点，则创建一个新的 Trie 节点 if (node->next[index] == NULL) { node->next[index] = new Trie(); } // 移动到下一个节点（即字符 c 对应的子节点） node = node->next[index]; } // 整个单词插入完成后，将最后一个字符对应的节点标记为单词结尾 node->isEnd = true; } // 在 Trie 中搜索一个完整的单词 // 如果单词存在且完整匹配，则返回 true；否则返回 false bool search(string word) { Trie* node = this; // 从根节点开始 // 遍历要搜索的单词中的每一个字符 for (char c : word) { // 计算字符对应的索引 int index = c - \'a\'; // 移动到对应的子节点 node = node->next[index]; // 如果在某一步，对应的子节点为 NULL，说明该路径不存在，即单词不存在 if (node == NULL) { return false; } } // 遍历完所有字符后，检查最后一个节点是否被标记为单词结尾 // 这是为了区分完整单词和仅是前缀的情况 // 例如，如果只插入了 \"apple\"，那么搜索 \"app\" 会到达一个节点，但其 isEnd 为 false，所以返回 false return node->isEnd; } // 判断 Trie 中是否存在以给定前缀开头的单词 // 只要前缀路径存在，就返回 true bool startsWith(string prefix) { Trie* node = this; // 从根节点开始 // 遍历前缀中的每一个字符 for (char c : prefix) { // 计算字符对应的索引 int index = c - \'a\'; // 移动到对应的子节点 node = node->next[index]; // 如果在某一步，对应的子节点为 NULL，说明没有单词以该前缀开头 if (node == NULL) { return false; } } // 如果成功遍历完前缀的所有字符，说明存在以该前缀开头的单词（至少有一个） return true; }};/** * 使用示例和说明： * * // 创建一个 Trie 对象（根节点） * Trie* obj = new Trie(); * * // 插入一个单词到 Trie 中 * obj->insert(\"apple\"); * * // 搜索一个完整的单词，返回 true 或 false * bool param_2 = obj->search(\"apple\"); // 返回 true * bool param_2b = obj->search(\"app\"); // 返回 false（如果只插入了 \"apple\"） * * // 检查是否存在以某个字符串为前缀的单词，返回 true 或 false * bool param_3 = obj->startsWith(\"app\"); // 返回 true * * 注意：使用 new 创建的对象需要在适当的时候用 delete 手动释放内存，避免内存泄漏。 */