LeetCode 热题100之图论

1.岛屿数量

思路分析：要计算一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格中的岛屿数量，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历每个岛屿。下面将展示使用 DFS 的方法。

• 遍历网格：遍历整个网络，检查每个位置；
• 发现岛屿：当找到一个‘1’陆地时，表示发现了一个新的岛屿。这时候用DFS来标记这个岛屿的所有部分。
• 标记已访问的部分：在DFS中，遍历所有相连的‘1’，并将它们标记为‘0’(已访问），以防止重复计算；
• 统计岛屿数量：每当我们找到一个新的’1’,就增加岛屿数量。

具体实现代码（详解版）：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0; // 如果网格为空，返回 0

        int numIslands = 0; // 岛屿数量
        int rows = grid.size(); // 行数
        int cols = grid[0].size(); // 列数

        // 遍历整个网格
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                // 当找到一个岛屿
                if (grid[r][c] == '1') {
                    numIslands++; // 岛屿数量增加
                    dfs(grid, r, c); // 使用 DFS 标记整个岛屿
                }
            }
        }

        return numIslands; // 返回岛屿数量
    }

private:
    // 深度优先搜索，标记岛屿
    void dfs(vector<vector<char>>& grid, int r, int c) {
        // 检查边界条件
        if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == '0') {
            return; // 如果越界或遇到水，返回
        }

        // 标记为已访问
        grid[r][c] = '0';

        // 继续探索上下左右四个方向
        dfs(grid, r + 1, c); // 向下
        dfs(grid, r - 1, c); // 向上
        dfs(grid, r, c + 1); // 向右
        dfs(grid, r, c - 1); // 向左
    }
};

• 时间复杂度：O（mn），其中m和n分别是网格的行数和列数；
• 空间复杂度：O（mn）.

2.腐烂的橘子

思路分析：这是一个典型的 多源广度优先搜索（BFS） 问题。在网格中，多源 BFS 可以帮助我们找到从多个起点到所有目标点的最短路径。因此，这个问题的核心思路是模拟腐烂橘子对周围新鲜橘子的传播过程，并统计所需的时间。

• 初始化与多源起点
  • 首先遍历整个网络，扎到所有腐烂橘子的初始位置，并将它们加到BFS队列中作为起点。每一个腐烂橘子会在接下来的分钟内使周围的新鲜橘子腐烂；
  • 同时统计网格中所有新鲜橘子的数量。如果没有新鲜橘子，则直接返回0，因为不需要任何传播。
• BFS传播腐烂：
  • 使用队列进行BFS，从所有橘子的初始位置开始逐层扩散。每一轮BFS表示一分钟，每一轮当中当前腐烂的橘子会使其周围的四个方向的新鲜橘子腐烂；
  • 每当新鲜橘子被腐烂时，新鲜橘子数减一，并将腐烂的新橘子位置加入队列，以便在下一分钟继续传播；
  • 每轮BFS完成后，计时器加1表示过去了一分钟。
• 终止条件
  • 当BFS结束时，由两种可能的情况：
    • 新鲜橘子全部腐烂：这时freshOranges为0，返回经过的分钟数，minutes；
    • 剩余橘子无法别腐烂：BFS 结束后，如果仍然有新鲜橘子（freshOranges > 0），则说明存在无法到达的新鲜橘子（如被空格隔开），返回 -1 表示不可能全部腐烂。

为什么选择 BFS？

• BFS 的特性是逐层扩散，先将距离起点近的节点（橘子）处理完，再扩展到更远的节点，因此适合这种求最短传播路径的问题。
  因为腐烂橘子可以同时腐烂周围新鲜橘子，BFS 可以在同一时间处理多个腐烂橘子的传播过程，非常适合这种多源扩展的情景。

具体实现代码（详解版）：

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();//行数
        int n = grid[0].size();//列数

        queue<pair<int, int>> rotten; // 队列，用于存储当前腐烂橘子的坐标
        int freshOranges = 0; // 记录新鲜橘子的总数

        // 初始化：将所有腐烂橘子的位置加入队列，同时统计新鲜橘子的数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    rotten.push({i, j}); // 腐烂橘子加入队列
                } else if (grid[i][j] == 1) {
                    freshOranges++; // 统计新鲜橘子的数量
                }
            }
        }
        // 边界情况：如果没有腐烂橘子，直接返回0
        if (freshOranges == 0)
            return 0;

        int minutes = 0; // 记录分钟数
        vector<pair<int, int>> directions = {
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向

        // 开始进行BFS，每一轮扩散代表一分钟
        while (!rotten.empty()) {
            int size = rotten.size(); // 当前层的腐烂橘子的数量
            bool foundFresh = false; // 标记是否有橘子在这一轮被腐烂
            // 遍历当前层的腐烂橘子
            for (int i = 0; i < size; i++) {
                auto [x, y] = rotten.front(); // 当前腐烂橘子的坐标
                rotten.pop(); // 将当前腐烂橘子从队列中移除
                // 尝试向四个方向扩散腐烂
                for (auto [dx, dy] : directions) {
                    int nx = x + dx;
                    int ny = y + dy;

                    // 检查新位置是否在边界内并且是否为新鲜橘子
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                        grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;      // 将新鲜橘子腐烂
                        rotten.push({nx, ny}); // 新腐烂的橘子加入队列
                        freshOranges--;        // 新鲜橘子减少
                        foundFresh = true; // 标记为找到新腐烂的橘子
                    }
                }
            }
            //如果这一轮中有新鲜橘子腐烂，则时间加1
            if (foundFresh)
                minutes++;
        }
        //检查是否还有剩余的新鲜橘子，如果有返回-1，否则返回所需要的分钟数
        return freshOranges == 0 ? minutes : -1;
    }
};

• 时间复杂度：O（mn），其中m,n分别是网格的行数和列数
• 空间复杂度：O（mn）.

3.课程表

这个问题可以用 拓扑排序 或 图的环检测 来解决。问题的核心在于确定是否存在一个课程学习顺序，使得可以满足所有的先修课程要求。如果出现环（即某个课程的先修要求出现了循环依赖），那么这个顺序就不可能存在，从而课程无法全部完成。

思路分析1（DFS):在有向图中，我们可以通过 DFS 来检测是否存在环。如果存在环，则无法完成所有课程的学习；如果没有环，则可以完成所有将课程。

• 建模为有向图：将课程和先修关系建模为有向图，其中每个课程是一个节点，先修关系表示一条从前置课程到后续课程的有向边。
• DFS检测环：
  • 使用 DFS 遍历图中的每个节点。
  • 每个节点可以有3种状态：
    • 未访问（0）：节点还未被访问；
    • 正在访问（1）：节点在当前的DFS路径上。若在DFS过程中再次遇到此状态的节点，说明存在环；
    • 已访问（2）：节点已经被完全处理，不再在当前的路径中。
  • 当我们从一个节点开始DFS时，把它标记为”正在访问“。如果在DFS种再次访问到一个”正在访问“的节点，说明存在环；
  • DFS完成后，将节点标记未”已访问：，表示这个节点的所有邻居节点都已经处理完毕，不会再引起环
• 初始化每个节点的状态为“未访问”。
• 对每个节点调用 DFS。如果 DFS 中检测到环，直接返回 false；如果所有节点都遍历完成且无环，返回 true。

具体实现代码（详解版）：

class Solution {
public:
    bool dfs(int course, vector<vector<int>>& adjList, vector<int>& status) {
        // 表示在当前 DFS 路径中再次遇到 course，说明存在环，返回 true。
        if (status[course] == 1)
            return true;

        // course 已经处理完毕，不再需要检查，返回 false
        if (status[course] == 2)
            return false;

        status[course] = 1; // 标记当前节点为正在访问
        // 遍历当前课程的所有后续课程
        for (int nextCoures : adjList[course]) {
            if (dfs(nextCoures, adjList, status)) {
                return true;
            }
        }
        status[course] = 2; // 标记为已访问
        return false;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建邻接表
        vector<vector<int>> adjList(numCourses);
        for (const auto& pre : prerequisites) {
            int course = pre[0];
            int preCourse = pre[1];
            adjList[preCourse].push_back(course);
        }
        // 状态数组：0未访问；1-正在访问；2已访问
        vector<int> status(numCourses, 0);
        // 对每个课程进行DFS，如果检测到环，则无法完成所有课程
        for (int course = 0; course < numCourses; course++) {
            if (status[course] == 0) {
                if (dfs(course, adjList, status)) {
                    return false; // 存在环，返回false
                }
            }
        }
        return true; // 无环，表示可以完成所有课程
    }
};

思路分析2（拓扑排序）：基于入度（进入某节点的边数），在入度为零的节点中依次取出节点并删除边，直到无法删除新的节点。如果最后所有节点都被删除，则无环，否则有环。入度可以理解为一个课程在学习之前必须完成的先修课程数。如果课程的入度为 0，说明它可以直接学习，不需要其他课程作为前置条件。拓扑排序通过不断消除入度为 0 的节点来确保学习顺序，类似“逐层剥洋葱”。如果最终还能剩下课程无法剥离，说明存在环。

• 构建入度和邻接表
  • indegree 数组用于记录每门课程的入度（即需要的先修课程数量）。
  • adjList 是邻接表，用于记录每门课程指向的后续课程。
• 初始化队列：将所有入度为 0 的课程加入队列，这些课程可以直接开始学习，不依赖其他课程
• 拓扑排序：
  • 每次从队列中取出一个入度为 0 的课程，计数已完成的课程数。
  • 对于该课程的后续课程，减少其入度，如果入度变为 0，则加入队列，表示该课程的前置课程已完成，可以开始学习。
  • 结果判断：最后，如果处理过的课程数量等于总课程数，则说明无环，返回 true。否则，返回 false，表示有环，无法完成所有课程。

具体实现代码（详解版）：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //构建图的入度表和邻接表
        vector<int> indegree(numCourses,0);//入度表，记录没门课程的前置课程数量
        vector<vector<int>> adjList(numCourses);//邻接表，记录每门课程指向的后续课程

        //填充入读表和邻接表
        for(const auto& pre : prerequisites){
            int course = pre[0];
            int preCourse = pre[1];
            adjList[preCourse].push_back(course);//建立前置课程到后续课程的有向边
            indegree[course] ++;//该课程的入度加1
        }

        //初始化队列，将所有入度为0的课程加入队列
        queue<int> q;
        for(int i = 0 ; i < numCourses ; i ++){
            if(indegree[i] == 0){
                q.push(i);//入度为0的课程可以直接学习
            }
        }
        int completeCourses = 0;//记录已完成课程的数量

        //拓扑排序过程
        while(!q.empty()){
            int course = q.front();//取出一个入度为0的课程
            q.pop();
            completeCourses ++;//完成该课程

            //遍历该课程的后续课程，减少后续课程的入度
            for(int nextCourse : adjList[course]){
                indegree[nextCourse] --;//减少后续课程的入度
                if(indegree[nextCourse] == 0){//后续课程的入度变为0
                    q.push(nextCourse);//将其加入队列，以便在下一轮可以直接学习
                }
            }
        }
        return completeCourses == numCourses;

    }
};

• 时间复杂度：DFS 和 拓扑排序 的时间复杂度都是 O(V+E)，其中 V 是课程的数量，即 numCourses，而 E 是先修课程对的数量，即 prerequisites.size()。适合稀疏图的情况（即边数远小于节点数的平方）。
• 空间复杂度: 两种方法的空间复杂度也都是 O(V+E)。
  这两种方法在时间和空间复杂度上几乎相同，选择方法时可以根据代码实现的简单性和使用的图遍历方式来决定。DFS 更适合递归结构，而拓扑排序使用了入度表和队列的迭代结构。

4.实现Trie（前缀树）

思路分析：

• 初始化 Trie 对象时，会创建一个根节点
• insert 方法：遍历单词的每个字符，依次检查每个字符是否在当前节点的 children 中。若不存在，则创建一个新节点并加入 children。遍历完成后，将最后一个字符对应的节点标记为单词结尾。
• search 方法：遍历单词的每个字符，逐级检查是否存在相应的字符路径。如果路径存在且最后节点标记为单词结尾，则返回 true，否则返回 false。
• startsWith 方法：与 search 方法类似，但不要求最后一个节点为单词结尾，只需检查是否存在该前缀的路径。

具体实现代码（详解版）：

class Trie {
private:
    // 子节点数组，大小为 26，用于表示每个小写字母的子节点
    vector<Trie*> children;
    // 标记当前节点是否为某个单词的结束节点
    bool isEnd;

    // 辅助函数：查找指定前缀的节点
    Trie* searchPrefix(string prefix) {
        // 从当前节点开始查找
        Trie* node = this; 
        // 遍历前缀中的每个字符
        for (char ch : prefix) {
            ch -= 'a'; // 将字符转换为对应的索引（0-25）
            // 如果当前节点的子节点中没有对应的字符，返回 nullptr
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            // 移动到下一个节点
            node = node->children[ch];
        }
        // 返回找到的节点
        return node;
    }

public:
    // 构造函数：初始化子节点和结束标志
    Trie() : children(26, nullptr), isEnd(false) {}

    // 插入单词
    void insert(string word) {
        Trie* node = this; // 从根节点开始
        // 遍历单词中的每个字符
        for (char ch : word) {
            ch -= 'a'; // 将字符转换为对应的索引（0-25）
            // 如果当前节点的子节点中没有对应的字符，创建新节点
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            // 移动到下一个节点
            node = node->children[ch];
        }
        // 将最后一个字符的节点标记为单词的结束
        node->isEnd = true;
    }

    // 搜索完整单词
    bool search(string word) {
        Trie* node = this->searchPrefix(word); // 查找单词对应的节点
        // 返回节点是否存在且为单词结束节点
        return node != nullptr && node->isEnd;
    }

    // 检查是否存在以指定前缀开头的单词
    bool startsWith(string prefix) {
        // 只需查找前缀对应的节点是否存在即可
        return this->searchPrefix(prefix) != nullptr;
    }
};

/**
 * 例子使用：
 * Trie* obj = new Trie();
 * obj->insert(word);       // 插入单词
 * bool param_2 = obj->search(word);     // 搜索完整单词
 * bool param_3 = obj->startsWith(prefix); // 检查前缀
 */

这个题目在很多大厂面试的时候都会被问到，应该重点关注~