【C++】拓扑排序(BFS)

啊QQQQQ

发布于 2024-11-19 19:13:01

3140

文章被收录于专栏：C++C++

拓扑排序介绍

有向无环图

入度：指向活动节点的箭头个数；出度：从活动节点出去指向别的节点的箭头个数。

通过入度和出入我们可以判断活动的进行顺序，活动度数为0的活动先进行没进行完后，将该活动的出度清空，下一个入度为0的节点就是该节点之后要进行的活动，以此类推，直到最后没有活动节点，如果只存在有一个入度的节点(成环)。

如何解决这类问题

1.首先建图，也就是邻接矩阵，可以使用哈希表处理。 2.统计所有活动节点的出度和入度。 3.如果入度是0就把活动节点加入到队列中。 4.BFS每走一步就把该节点的出度清空，将下一个入度为0的节点加入队列中。 5.判断是否有环：遍历度数表，如果还存在度数不为0的活动节点，那么说明还有活动成环了；

课程表

地址：. - 力扣（LeetCode）

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

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

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

算法思路

原问题可以转换成⼀个拓扑排序问题。

⽤ BFS 解决拓扑排序即可。

拓扑排序流程：

a. 将所有⼊度为 0 的点加⼊到队列中；

b. 当队列不空的时候，⼀直循环：

i. 取出队头元素；

ii. 将于队头元素相连的顶点的⼊度 - 1；

iii. 然后判断是否减成 0,。如果减成 0，就加⼊到队列中。

代码实现

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //首先构造邻接矩阵,也就是边
        int n=numCourses;
        unordered_map<int,vector<int>>edge;
        //储存每一个节点的入度
        //先把所有的节点放在了数组中
        vector<int>in(n);//后面要统计所有课程的度数是否为零
        //储存所有的边
        for(auto &x:prerequisites)
        {
            int a=x[0];//最红的课程(终点)
            int b=x[1];//先学的课程(起点)
            //存进数组中
            edge[b].push_back(a);
            in[a]++;//对应节点的入度增加
        }
        //开始使用队列来处理无度数的节点
        queue<int>q;
        for(int i=0;i<n;i++)
        if(in[i]==0)
        q.push(i);//如果入度为零，就加入到队列
        while(q.size())
        {
            //取出无度数的节点
            auto tmp=q.front();
            q.pop();
            //然后取消所有与他有关的边
            for(auto& x: edge[tmp])
            {
                in[x]--;
                //是否要加入后面的课程
                if(in[x]==0)//如果没有度数了
                {
                    q.push(x);
                }
            }

        }
        //判断是否有环
        for(auto i:in)
        {
            if(i)//如果存在度数不为0的节点
            return false;
        }
        return true;
    }
};

课程表2

地址：. - 力扣（LeetCode）

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

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3]

示例 3：

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

算法思路

与上一道题一样。

代码实现

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& p) {
            unordered_map<int,vector<int>>edge;
            //储存所有的节点
            vector<int>in(n);//统计所有节点的度数
 
            //建图
            for(auto &e:p)
            {
                int a=e[0];//终点
                int b=e[1];//起点
                edge[b].push_back(a);
                in[a]++;//终点的入度数增加
            }
 
            //DFS
            queue<int>q;
            for(int i=0;i<n;i++)
            if(in[i]==0)
            q.push(i);//储存所有的入度为零的节点.
            //储存结果的数组
            vector<int>ret;
            while(q.size())
            {
                auto t=q.front();
                q.pop();
                ret.push_back(t);
                for(auto x:edge[t])//遍历节点后的链接的节点
                {
                    in[x]--;
                    if(in[x]==0)
                    {
                        q.push(x);
                    }
                }
            }
            //判断是否有环
            for(auto x:in)
            if(x)return {};
            return ret;
    }
};

火星词典

地址：. - 力扣（LeetCode）

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

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

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

字符串 s 字典顺序小于 字符串 t 有两种情况：

在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

示例 1：

输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"

示例 2：

输入：words = ["z","x"]
输出："zx"

示例 3：

输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。

代码实现

class Solution {
public:
    unordered_map<char,unordered_set<char>>edge;
    unordered_map<char,int>in;
    string alienOrder(vector<string>& words) {
        for(auto &str:words)
        {
            for(auto x:str)
            {
                in[x]=0;
            }
        }
        int n=words.size();
        for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            bool tmp=add(words[i],words[j]);
            if(tmp==true)return "";
        }
 
        queue<char>q;
        for(auto [a,b]:in)
        {
            if(b==0)q.push(a);
        }
        string ret;
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            ret+=t;
            for(auto x:edge[t])
            {
                if(--in[x]==0)q.push(x);
            }
        }
 
        for(auto [a,b]:in)
        if(b)return "";
        return ret;
    }
 
 
    bool 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];
                char b=s2[i];
                if(!edge.count(a)||!edge[a].count(b))
                {
                    edge[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
        if(i==s2.size()&&i<s1.size())return true; 
        return false;
    }
};