当前位置：首页 > news >正文

算法笔记（十五）——BFS 解决拓扑排序

news 2025/3/11 6:15:31

文章目录

拓扑排序
课程表
课程表 II
火星词典

拓扑排序

有向无环图（DAG图）

有向无环图指的是一个无回路的有向图

在这里插入图片描述

AOV网：顶点活动图

在有向无环图中，用顶点表示一个活动，用边来表示活动的先后顺序的图结构

拓扑排序

找到一个先后顺序，结果可能不唯一

如何拓扑排序？
- 找到一个入度为零的点，然后输出；
- 删除与该点连接的边；
- 重复上述操作，直至图中没有点或没有入度为零的点（图中有环）；

实现拓扑排序

初始化：将所有入度为0的点加入到队列中
当队列不空的时候，循环：
1. 拿出队头元素，加入到结果中
2. 删除与该元素相连的边
3. 判断：与删除边相连的点入度是否为0；如果为0，将该点加入队列

课程表

题目：课程表

在这里插入图片描述

思路

建立哈希表unordered_map<int, vector<int>> edges;存储有向图的边，edges[b].push_back(a);表示b->a
用vector<int> in(numCourses);来表示节点的入度
利用上述容器建图
将入度为 0的节点加入队列q
BFS进行拓扑排序，入度为0的节点依次出队，并将其邻接节点的入度减1。如果邻接节点的入度减为0，将其加入队列
判断是否有环：vector<int> in(numCourses);中入度都为0即不存在环，返回true

C++代码

class Solution 
{
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 1. 初始化unordered_map<int, vector<int>> edges;vector<int> in(numCourses);// 2. 建图for(auto& e : prerequisites){int a = e[0], b = e[1];edges[b].push_back(a);in[a]++;}// 3.拓扑排序queue<int> q;// 入度为 0 的点进队for(int i = 0; i < numCourses; i++){if(in[i] == 0) q.push(i);}// BFSwhile(!q.empty()){auto t = q.front(); q.pop();for(auto e : edges[t]){in[e]--;if(in[e] == 0) q.push(e);}}// 4. 判断是否有环for(auto e : in){if(e) return false;}return true;}
};

课程表 II

题目：课程表 II

在这里插入图片描述
思路

思路和上面一致，只需要在每次将入度为0的点顺序保存即为拓扑排序的顺序。

C++代码

class Solution 
{
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {// 1. 初始化unordered_map<int, vector<int>> edges;vector<int> in(numCourses);// 2. 建图for(auto& e : prerequisites){int a = e[0], b = e[1];edges[b].push_back(a);in[a]++;}// 3.拓扑排序queue<int> q;vector<int> ret;// 入度为 0 的点进队for(int i = 0; i < numCourses; i++){if(in[i] == 0) q.push(i);}// BFSwhile(!q.empty()){auto t = q.front(); q.pop();ret.push_back(t);for(auto e : edges[t]){in[e]--;if(in[e] == 0) q.push(e);}}for(auto e : in){if(e) return {};}return ret;}
};

火星词典

题目：火星词典

在这里插入图片描述

思路

理解题意：

如何搜集信息：

两层for循环枚举所有的两个字符串组合
利用双指针，找出字典序规则信息

建图和初始化入度信息

unordered_map<char, unordered_set<char>> edges; // 邻接表存储图
unordered_map<char, int> in; // 节点入度

添加边和检测冲突
1. 对于单词列表中的每一对单词，比较它们相同位置上的字符。如果找到第一个不同的字符，则添加一条从该字符到另一个字符的边，并增加目标字符的入度。
2. 如果一个单词是另一个单词的前缀且更长，则这表示存在冲突（因为按照字典序，更长的单词不应该出现在更短的单词之后），此时设置check为true并返回空字符串表示无解
拓扑排序
1. 将所有入度为0的节点（字母）加入队列
2. 取出节点，将其添加到结果字符串中，并减少其所有邻接节点的入度。如果某个邻接节点的入度变为0，则将其加入队列
3. 重复上述过程直到队列为空
判断成环：检查是否所有节点的入度都为0

C++代码

class Solution 
{unordered_map<char, unordered_set<char>> edges; // 邻接表存储图unordered_map<char, int> in; // 节点入度bool check = false;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]){// a -> bchar a = s1[i], b = s2[i];if(!edges.count(a) || !edges[a].count(b)){edges[a].insert(b);in[b]++;}break;}}if(i == s2.size() && i < s1.size()) check = true;}
public:string alienOrder(vector<string>& words) {// 1. 建图 + 初始化入度信息for(auto word : words)for(auto ch : word)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(check) return "";}}// 2.拓扑排序queue<char> q;for(auto& [a, b] : in)if(b == 0) q.push(a);string ret;while(!q.empty()){char t = q.front(); q.pop();ret += t;for(auto ch : edges[t]){in[ch]--;if(in[ch] == 0) q.push(ch);}}// 3.判断成环for(auto& [a, b] : in)if(b) return "";return ret;}
};