算法笔记（十五）——BFS 解决拓扑排序
文章目录
- 拓扑排序
- 课程表
- 课程表 II
- 火星词典
拓扑排序
有向无环图（DAG图）
- 有向无环图指的是一个无回路的有向图
AOV网：顶点活动图
在有向无环图中，用顶点表示一个活动，用边来表示活动的先后顺序的图结构
拓扑排序
- 找到一个先后顺序，结果可能不唯一
- 如何拓扑排序？
-
- 找到一个入度为零的点，然后输出；
-
- 删除与该点连接的边；
-
- 重复上述操作，直至图中没有点或没有入度为零的点（图中有环）；
- 实现拓扑排序
- 初始化：将所有入度为0的点加入到队列中
- 当队列不空的时候，循环：
- 拿出队头元素，加入到结果中
- 删除与该元素相连的边
- 判断：与删除边相连的点入度是否为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);
}
// BFS
while(!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);
}
// BFS
while(!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; // 节点入度
-
添加边和检测冲突
- 对于单词列表中的每一对单词，比较它们相同位置上的字符。如果找到第一个不同的字符，则添加一条从该字符到另一个字符的边，并增加目标字符的入度。
- 如果一个单词是另一个单词的前缀且更长，则这表示存在冲突（因为按照字典序，更长的单词不应该出现在更短的单词之后），此时设置
check为true并返回空字符串表示无解
-
拓扑排序
- 将所有入度为0的节点（字母）加入队列
- 取出节点，将其添加到结果字符串中，并减少其所有邻接节点的入度。如果某个邻接节点的入度变为0，则将其加入队列
- 重复上述过程直到队列为空
-
判断成环：检查是否所有节点的入度都为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 -> b
char 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;
}
};