【优选算法】BFS解决拓扑排序

拓扑排序简介

1. 有向无环图（DAG图）

DAG 的核心特征：

• 有向性：图中的边具有方向
• 无环性：不存在任何闭合路径
• 拓扑排序存在性：DAG 的重要性质是必然可以进行拓扑排序

2. 入度和出度

• 入度：对于有向图中的某个顶点 V，入度是指以 V 为终点的有向边的数量，即所有指向 V 的边的总数
• 出度：对于有向图中的某个顶点 V，出度是指以 V 为起点的有向边的数量，即所有从 V 出发的边的总数

3. 顶点活动图（AOV 图）

顶点活动图是一种特殊的有向无环图，其中顶点表示活动（任务），边表示活动之间的依赖关系。AOV 图常用于表示任务调度、工程进度安排等场景，通过拓扑排序可确定活动的执行顺序。

AOV的核心概念：

• 顶点（Vertex）：
  • 表示具体的活动或任务
  • 每个顶点可能有前置条件（必须完成的其他活动）和后续活动（依赖于当前活动的活动）
• 边（Edge）：
  • 表示活动之间的依赖关系，若存在边 A → B，则表示活动 A 必须在 B 开始前完成
  • 边具有方向性且无环

4. 拓扑排序

拓扑排序是对有向无环图的顶点进行排序的一种算法，其核心目标是将所有顶点排成一个线性序列，使得图中任意一条有向边的起点在序列中都出现在终点之前。拓扑排序的结果可能不是唯一的。

如何进行排序：

1. 找到图中入度为0的点，然后输出
2. 删除与点相连的边
3. 重复1、2操作，直到图中没有点或者没有入度为0的点（有可能有环）

拓扑排序一个重要的应用就是判断有向图中是否有环。

5. 实现拓扑排序

拓扑排序需要借助队列，来一次BFS实现。

1. 将所有入度为0的点加入到队列中
2. 当队列不为空时（循环）：
   • 拿出队头元素，加入到最终结果中
   • 删除与该元素相连的所有边
   • 判断与删除元素相邻的点，是否入度变为了0，如果入度为0，将该元素加入到队列中

一、课程表

题目描述：

思路讲解：
本道题需要我们判断是否能完成所有课程的学习，本质是判断课程依赖关系构成的有向图是否存在环。若存在环，则无法完成所有课程；否则可以。使用BFS 拓扑排序可以解决此类问题，通过逐层移除入度为 0 的节点，最终判断是否所有节点都被处理。以下是具体思路：

1. 邻接表 um 存储每个课程的后续课程列表（即学完当前课程后可以学习哪些课程），入度数组 in 记录每个课程的前置课程数量
2. 将所有入度为 0 的课程加入队列
3. BFS 处理队列：
   • 每次从队列中取出一个课程，将其后续课程的入度减 1
   • 若某个后续课程的入度变为 0，将其加入队列
4. 若最终入度数组 in 中课程的入度都为0，说明所有课程都被处理，无环；否则存在环

编写代码：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int,vector<int>> um;
        vector<int> in(numCourses,0);

        for(auto& prs : prerequisites)
        {
            int a = prs[0] , b = prs[1]; // b -> a

            um[b].push_back(a);
            in[a]++;
        }

        queue<int> qu;
        for(int i = 0 ; i < numCourses ; i++)
        {
            if(in[i] == 0)
            {
                qu.push(i);
            }
        }

        while(!qu.empty())
        {
            int cour = qu.front();
            qu.pop();

            for(auto x : um[cour])
            {
                in[x]--;
                if(in[x] == 0)  qu.push(x);
            }
        }

        for(int i = 0 ;  i < numCourses ; i++)
        {
            if(in[i] != 0)  return false;
        }

        return true;
    }
};

二、课程表 II

题目描述：

思路讲解：
本道题需要我们找到课程学习顺序，思路与上一题完全一致，使用拓扑排序判断判断课程依赖关系构成的有向图是否存在环，如果无环则返回拓扑排序中取出课程的顺序，否则返回空数组。以下是具体思路：

1. 邻接表 um 存储每个课程的后续课程列表（即学完当前课程后可以学习哪些课程），入度数组 in 记录每个课程的前置课程数量，结果数组用来存储课程顺序
2. 将所有入度为 0 的课程加入队列
3. BFS 处理队列：
   • 每次从队列中取出一个课程，将其后续课程的入度减 1，并加入到结果数组中
   • 若某个后续课程的入度变为 0，将其加入队列
4. 若最终入度数组 in 中课程的入度都为0，说明所有课程都被处理，有向图无环，返回结果数组；否则存在环，返回空数组

编写代码：

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int,vector<int>> um;
        vector<int> in(numCourses);

        for(auto& prs : prerequisites)
        {
            int a = prs[0] , b = prs[1];  // b -> a

            um[b].push_back(a);
            in[a]++;
        }

        queue<int> qu;
        for(int i = 0 ; i < numCourses ; i++)
        {
            if(in[i] == 0)  qu.push(i);
        }

        vector<int> ans;

        while(!qu.empty())
        {
            int cour = qu.front();
            ans.push_back(cour);
            qu.pop();

            for(auto x : um[cour])
            {
                in[x]--;

                if(in[x] == 0)  qu.push(x);
            }
        }
    
        for(int i = 0 ; i < numCourses ; i++)
        {
            if(in[i] != 0)  return vector<int>();
        }

        return ans;
    }
};

三、火星词典

题目描述：

思路讲解：
本道题需要我们根据给定的已排序字符串列表还原出外星语言的字母顺序。这本质上是一个拓扑排序问题，通过比较相邻字符串的首个不同字符来构建字母之间的依赖关系，然后使用 BFS 生成合法的字母顺序。以下是具体思路：

1. 遍历相邻字符串对，找到首个不同字符，建立依赖关系；邻接表 ans 存储每个字符的后续字符列表；入度数组 in 记录每个字符的前置字符数量；结果字符串存储字母顺序
2. 将所有入度为 0 的字符加入队列
3. BFS 处理队列：
   • 每次从队列中取出一个字符，将其加入结果字符串，并将其后续字符的入度减 1。
   • 若某个后续字符的入度变为 0，将其加入队列
4. 若最终入度数组 in 中课程的入度都为0，说明所有字符都被处理，无环返回结果字符串；否则存在环，返回空字符串

注意：处理前缀情况（如 “abc” 在 “abcd” 前是合法的，但 “abcd” 在 “abc” 前是非法的），遇到非法情况，可以直接返回空字符串。

编写代码：

class Solution {
    unordered_map<char,unordered_set<char>> um;
    unordered_map<char,int> in;
public:

    string alienOrder(vector<string>& words) {
        for(auto& word : words)
        {
            for(auto& ch : word)
            {
                in[ch] = 0;
            }
        }

        int size = words.size();
        for(int i = 0 ; i < size - 1 ; i++)
        {
            for(int j = i + 1 ; j < size ; j++)
            {
                string& str1 = words[i];
                string& str2 = words[j];

                int len1 = str1.size();
                int len2 = str2.size();
                int len = min(len1,len2);

                int pos = 0;
                for(; pos < len ; pos++)
                {
                    char ch1 = str1[pos] , ch2 = str2[pos];
                    if(ch1 != ch2)
                    {
                        if(um[ch1].find(ch2) == um[ch1].end())
                        {
                            um[ch1].insert(ch2);
                            in[ch2]++;
                        }
                        break;
                    }
                }

                if(pos == len2 && len1 > len2)
                    return "";
            }
        }

        queue<char> qu;
        for(auto& tmp : in)
        {
            if(tmp.second == 0)
            {
                qu.push(tmp.first);
            }
        }

        string ans;

        while(!qu.empty())
        {
            char ch = qu.front();
            ans += ch;
            qu.pop();

            for(auto& c : um[ch])
            {
                if(--in[c] == 0)  qu.push(c);
            }
        }

        for(auto& tmp : in)
        {
            if(tmp.second != 0) return "";
        }

        return ans;
    }
};

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹