刷题训练之 BFS 解决拓扑排序

დ旧言~

1295人浏览 · 2024-10-23 21:45:11

დ旧言~ · 2024-10-23 21:45:11 发布

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握 BFS 解决拓扑排序算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

基本思想：

🌙topic-->1

题目链接：1. - 力扣（LeetCode）

题目分析：

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

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

算法原理：

解法：BFS 拓扑排序

图解：

代码演示：

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& p) {
        unordered_map<int, vector<int>> edges; // 邻接表
        vector<int> in(n);                     // 存储每⼀个结点的⼊度
        // 1. 建图
        for (auto& e : p) {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }
        // 2. 拓扑排序 - bfs
        queue<int> q;
        // 把所有⼊度为 0 的点加⼊到队列中
        for (int i = 0; i < n; i++) {
            if (in[i] == 0)
                q.push(i);
        }
        // 层序遍历
        while (!q.empty()) {
            int t = q.front();
            q.pop();
            // 修改相连的边
            for (int e : edges[t]) {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }
        }
        // 3. 判断是否有环
        for (int i : in)
            if (i)
                return false;
        return true;
    }
};

🌙topic-->2

题目链接：2. - 力扣（LeetCode）

题目分析：

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

算法原理：

解法：BFS 拓扑排序

图解：本质和上面的题型一样，这里就不再赘述了。

代码演示：

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 1. 准备⼯作
        vector<vector<int>> edges(numCourses); // 邻接表存储图
        vector<int> in(numCourses);            // 存储每⼀个点的⼊度
        // 2. 建图
        for (auto& p : prerequisites) {
            int a = p[0], b = p[1]; // b -> a
            edges[b].push_back(a);
            in[a]++;
        }
        // 3. 拓扑排序
        vector<int> ret; // 统计排序后的结果
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0)
                q.push(i);
        }
        while (q.size()) {
            int t = q.front();
            q.pop();
            ret.push_back(t);
            for (int a : edges[t]) {
                in[a]--;
                if (in[a] == 0)
                    q.push(a);
            }
        }
        if (ret.size() == numCourses)
            return ret;
        else
            return {};
    }
};

🌙topic-->3

题目链接：3. - 力扣（LeetCode）

题目分析：

现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。

给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。

请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。

算法原理：

解法：BFS 拓扑排序

图解：

代码演示：

class Solution {
    unordered_map<char, unordered_set<char>> edges; // 邻接表来存储图
    unordered_map<char, int> in;                    // 统计⼊度
    bool cheak;                                     // 处理边界情况
public:
    string alienOrder(vector<string>& words) {
        // 1. 建图 + 初始化⼊度哈希表
        for (auto& s : words) {
            for (auto ch : s) {
                in[ch] = 0;
            }
        }
        int n = words.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                add(words[i], words[j]);
                if (cheak)
                    return "";
            }
        }
        // 2. 拓扑排序
        queue<char> q;
        for (auto& [a, b] : in) {
            if (b == 0)
                q.push(a);
        }
        string ret;
        while (q.size()) {
            char t = q.front();
            q.pop();
            ret += t;
            for (char ch : edges[t]) {
                if (--in[ch] == 0)
                    q.push(ch);
            }
        }
        // 3. 判断
        for (auto& [a, b] : in)
            if (b != 0)
                return "";
        return ret;
    }
    void add(string& s1, string& s2) {
        int n = min(s1.size(), s2.size());
        int i = 0;
        for (; i < n; i++) {
            if (s1[i] != s2[i]) {
                char a = s1[i], b = s2[i]; // a -> b
                if (!edges.count(a) || !edges[a].count(b)) {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
        if (i == s2.size() && i < s1.size())
            cheak = true;
    }
};