在力扣（LeetCode）平台上，图论相关的题目是算法面试和练习中的重要部分。今天，我们就来详细解析图论专题中的几道经典题目，帮助大家更好地理解解题思路和技巧。

一、岛屿数量（题目 200）

1. 题目描述

给定一个由 ‘0’（水）和 ‘1’（陆地）组成的二维网格，计算其中岛屿的数量。岛屿被水包围，且由相邻的陆地相连（水平或垂直）。

2. 示例

示例 1：

输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]

输出：1

示例 2：

输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

输出：3

3. 解题思路

这道题主要考察深度优先搜索（DFS）或广度优先搜索（BFS）的应用。我们可以遍历网格中的每个元素，当遇到陆地时，将其标记为已访问，并递归或迭代地访问其相邻的陆地，直到所有相连的陆地都被访问过。

4. 代码实现（Java）

java">public class Solution {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int rows = grid.length;int cols = grid[0].length;int count = 0;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == '1') {count++;dfs(grid, i, j);}}}return count;}private void dfs(char[][] grid, int i, int j) {if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {return;}grid[i][j] = '0';dfs(grid, i + 1, j);dfs(grid, i - 1, j);dfs(grid, i, j + 1);dfs(grid, i, j - 1);}
}

5. 复杂度分析

• 时间复杂度 ：O(m * n)，其中 m 和 n 分别是网格的行数和列数。我们需要遍历每个元素一次。
• 空间复杂度 ：O(m * n)，在最坏情况下，递归调用栈的深度可能达到 m * n。

二、腐烂的橘子（题目 994）

1. 题目描述

给定一个二维网格，其中 ‘0’ 表示空单元格，‘1’ 表示新鲜橘子，‘2’ 表示腐烂橘子。每分钟，腐烂的橘子会使其上下左右的新鲜橘子腐烂。返回所有新鲜橘子腐烂的最小分钟数。如果不可能，返回 -1。

2. 示例

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]

输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]

输出：-1

3. 解题思路

这道题主要考察广度优先搜索（BFS）的应用。我们可以将所有腐烂的橘子作为初始节点，同时进行 BFS，逐层腐烂相邻的新鲜橘子。在 BFS 过程中记录时间，并在最后检查是否还有新鲜橘子未腐烂。

4. 代码实现（Java）

java">import java.util.LinkedList;
import java.util.Queue;public class Solution {public int orangesRotting(int[][] grid) {int rows = grid.length;int cols = grid[0].length;Queue<int[]> queue = new LinkedList<>();int fresh = 0;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 2) {queue.offer(new int[]{i, j});} else if (grid[i][j] == 1) {fresh++;}}}if (fresh == 0) {return 0;}int minutes = 0;int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {int[] cell = queue.poll();for (int[] dir : directions) {int r = cell[0] + dir[0];int c = cell[1] + dir[1];if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1) {grid[r][c] = 2;fresh--;queue.offer(new int[]{r, c});}}}minutes++;}return fresh == 0 ? minutes - 1 : -1;}
}

5. 复杂度分析

• 时间复杂度 ：O(m * n)，其中 m 和 n 分别是网格的行数和列数。我们需要遍历每个元素一次。
• 空间复杂度 ：O(m * n)，在最坏情况下，队列中可能存储所有腐烂的橘子。

三、课程表（题目 207）

1. 题目描述

给定一个整数 numCourses 表示课程数目，以及一个列表 prerequisites，其中 prerequisites[i] = [ai, bi] 表示想要学习课程 ai 必须先学习课程 bi。判断是否可以完成所有课程。

2. 示例

示例 1：

输入：numCourses = 2, prerequisites = [[1, 0]]

输出：true

解释：可以先修课程 0，再修课程 1。

示例 2：

输入：numCourses = 2, prerequisites = [[1, 0], [0, 1]]

输出：false

解释：存在环，无法完成所有课程。

3. 解题思路

这道题主要考察拓扑排序的应用。我们可以使用广度优先搜索（BFS）来检测图中是否存在环。具体步骤如下：

1. 构建图的邻接表表示，并计算每个节点的入度。
2. 将入度为 0 的节点加入队列。
3. 遍历队列中的节点，减少其邻居节点的入度，如果邻居节点的入度变为 0，则加入队列。
4. 最后检查是否所有节点都被访问过，如果是，则可以完成所有课程；否则，存在环，无法完成。

4. 代码实现（Java）

java">import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> adj = new ArrayList<>();for (int i = 0; i < numCourses; i++) {adj.add(new ArrayList<>());}int[] inDegree = new int[numCourses];for (int[] pre : prerequisites) {adj.get(pre[1]).add(pre[0]);inDegree[pre[0]]++;}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}int count = 0;while (!queue.isEmpty()) {int node = queue.poll();count++;for (int neighbor : adj.get(node)) {inDegree[neighbor]--;if (inDegree[neighbor] == 0) {queue.offer(neighbor);}}}return count == numCourses;}
}

5. 复杂度分析

• 时间复杂度 ：O(V + E)，其中 V 是课程数目，E 是先修关系数目。我们需要遍历所有节点和边。
• 空间复杂度 ：O(V + E)，需要存储图的邻接表和入度数组。

四、实现 Trie（前缀树）（题目 208）

1. 题目描述

实现一个 Trie（前缀树），包含以下方法：

• Trie() ：初始化前缀树。
• insert(String word) ：将字符串 word 插入前缀树。
• search(String word) ：如果字符串 word 存在于前缀树中，则返回 true，否则返回 false。
• startsWith(String prefix) ：如果存在以 prefix 为前缀的字符串，则返回 true，否则返回 false。

2. 示例

示例 1：

输入：

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出：

[null, null, true, false, true, null, true]

3. 解题思路

这道题主要考察前缀树的实现。前缀树是一种树形数据结构，用于高效地存储和检索字符串集合。每个节点表示一个字符，并包含指向子节点的链接。具体步骤如下：

1. 创建一个 TrieNode 类，包含一个字符数组（或哈希表）来存储子节点，以及一个标志位表示是否是单词的结尾。
2. 在 Trie 类中，维护一个根节点，初始化时创建。
3. 插入操作：从根节点开始，逐字符遍历字符串，如果当前字符不存在于当前节点的子节点中，则创建新节点。遍历结束后，将最后一个节点的标志位置为 true。
4. 搜索操作：从根节点开始，逐字符遍历字符串，如果当前字符不存在于当前节点的子节点中，则返回 false。遍历结束后，检查最后一个节点的标志位是否为 true。
5. 前缀匹配操作：与搜索操作类似，但不需要检查标志位，只需要遍历完整个前缀即可。

4. 代码实现（Java）

java">class TrieNode {TrieNode[] children;boolean isEnd;public TrieNode() {children = new TrieNode[26];isEnd = false;}
}public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;for (char c : word.toCharArray()) {int index = c - 'a';if (node.children[index] == null) {node.children[index] = new TrieNode();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {TrieNode node = root;for (char c : word.toCharArray()) {int index = c - 'a';if (node.children[index] == null) {return false;}node = node.children[index];}return node.isEnd;}public boolean startsWith(String prefix) {TrieNode node = root;for (char c : prefix.toCharArray()) {int index = c - 'a';if (node.children[index] == null) {return false;}node = node.children[index];}return true;}
}

5. 复杂度分析

• 时间复杂度 ：对于插入、搜索和前缀匹配操作，时间复杂度均为 O(L)，其中 L 是字符串的长度。我们需要遍历每个字符一次。
• 空间复杂度 ：O(1)，每个节点的子节点数目固定为 26（假设只包含小写字母）。

以上就是力扣热题 100 中与图论相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。