LeetCode-13day:图论

题目方法时间复杂度空间复杂度岛屿数量深度优先搜索（DFS）O(m × n)O(m × n)腐烂的橘子多源 BFSO(m × n)O(m × n)课程表深度优先搜索（DFS）检测环O(n + m)O(n + m)实现 Trie (前缀树)Trie（字典树）O(L)O(T)

浩少702

1044人浏览 · 2025-08-04 16:20:27

浩少702 · 2025-08-04 16:20:27 发布

图论经典算法总结（C++实现）

图论是算法中的重要部分，广泛应用于各种实际问题中。本文总结了四道经典的图论问题，涵盖不同类型的算法技巧，帮助你更好地理解和掌握图论的操作。

🟢 1. 岛屿数量（Number of Islands）

📄 题目描述：

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

🧠 解题思路（简洁版）

深度优先搜索（DFS）：
- 遍历网格，遇到陆地（'1'）时，启动 DFS，将整个岛屿的陆地标记为水（'0'）。
- 每次启动 DFS 时，岛屿数量加一。

⏱️ 复杂度分析

时间复杂度：O(m × n)，其中 m 和 n 分别为网格的行数和列数。
空间复杂度：O(m × n)，递归栈空间。

✅ C++ 实现

class Solution {
public:
    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);
    }

    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; r++) {
            for (int c = 0; c < nc; c++) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }
        return num_islands;
    }
};

🟢 2. 腐烂的橘子（Rotting Oranges）

📄 题目描述：

给定一个二维网格，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。

每分钟，任何与腐烂橘子相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止的最小分钟数。如果不可能，则返回 -1。

🧠 解题思路（简洁版）

多源 BFS：
- 初始化队列，将所有腐烂的橘子入队，标记其距离为 0。
- 按层序扩展，将相邻的新鲜橘子标记为腐烂，并更新距离。
- 若所有新鲜橘子都被腐烂，则返回最大距离；否则返回 -1。

⏱️ 复杂度分析

时间复杂度：O(m × n)，其中 m 和 n 分别为网格的行数和列数。
空间复杂度：O(m × n)，队列和距离数组。

✅ C++ 实现

class Solution {
    int cnt;
    int dis[10][10];
    int dir_x[4] = {0, 1, 0, -1};
    int dir_y[4] = {1, 0, -1, 0};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;
        memset(dis, -1, sizeof(dis));
        cnt = 0;
        int n = grid.size(), m = grid[0].size(), ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.emplace(i, j);
                    dis[i][j] = 0;
                } else if (grid[i][j] == 1) {
                    cnt += 1;
                }
            }
        }
        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int tx = r + dir_x[i];
                int ty = c + dir_y[i];
                if (tx < 0 || tx >= n || ty < 0 || ty >= m || ~dis[tx][ty] || !grid[tx][ty]) {
                    continue;
                }
                dis[tx][ty] = dis[r][c] + 1;
                q.emplace(tx, ty);
                if (grid[tx][ty] == 1) {
                    cnt -= 1;
                    ans = dis[tx][ty];
                    if (!cnt) {
                        break;
                    }
                }
            }
        }
        return cnt ? -1 : ans;
    }
};

🟢 3. 课程表（Course Schedule）

📄 题目描述：

有 numCourses 门课程，它们按从 0 到 numCourses - 1 编号。你可能会获得一个先修课程列表，其中 prerequisites[i] 表示在修课程 i 之前必须先修课程 prerequisites[i][0]。判断是否可以完成所有课程。

🧠 解题思路（简洁版）

深度优先搜索（DFS）检测环：
- 构建邻接表表示课程的依赖关系。
- 使用 visited 数组标记节点状态（0：未访问，1：正在访问，2：已访问）。
- 遍历所有课程，对未访问的课程启动 DFS。
- 若在 DFS 中遇到正在访问的节点，则存在环，返回 false。
- 若所有课程都访问完成且无环，则返回 true。

⏱️ 复杂度分析

时间复杂度：O(n + m)，其中 n 是课程数，m 是先修条件数。
空间复杂度：O(n + m)，邻接表和访问状态数组。

✅ C++ 实现

class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

    void dfs(int u) {
        visited[u] = 1;
        for (int v : edges[u]) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info : prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
        for (int i = 0; i < numCourses && valid; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        return valid;
    }
};

🟢 4. 实现 Trie (前缀树)（Implement Trie）

📄 题目描述：

实现一个 Trie（前缀树），一个用于存储字符串集合的数据结构。实现以下功能：

insert(word)：将一个字符串插入到 Trie 中。
search(word)：判断 Trie 中是否存在一个完整的单词。
startsWith(prefix)：判断 Trie 中是否存在以给定前缀开头的单词。

🧠 解题思路（简洁版）

Trie（字典树）：
- 使用 Trie 结构存储字符串集合。
- 每个节点有 26 个子节点，分别对应小写字母。
- insert：逐字符插入，若子节点不存在则创建。
- search：查找完整单词，需检查是否为单词结尾。
- startsWith：查找前缀，只需检查路径是否存在。

⏱️ 复杂度分析

时间复杂度：O(L)，其中 L 为字符串长度。
空间复杂度：O(T)，其中 T 为所有字符串的字符总数。

✅ C++ 实现

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            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;
    }
};

📌 总结

题目	方法	时间复杂度	空间复杂度
岛屿数量	深度优先搜索（DFS）	O(m × n)	O(m × n)
腐烂的橘子	多源 BFS	O(m × n)	O(m × n)
课程表	深度优先搜索（DFS）检测环	O(n + m)	O(n + m)
实现 Trie (前缀树)	Trie（字典树）	O(L)	O(T)