BFS算法解决拓扑排序问题详解
BFS算法解决拓扑排序问题详解
拓扑排序是图论中的一个重要概念，常用于解决依赖关系问题。本文将通过BFS算法，详细讲解如何实现拓扑排序，并通过三个LeetCode题目进行实战演练。
关于拓扑排序
拓扑排序是一种对有向无环图（DAG）进行排序的算法，其目的是找出所有顶点的一个线性序列，使得对于每一条有向边(u, v)，顶点u在序列中都排在顶点v的前面。这种排序方式在很多实际问题中都有应用，比如课程安排、任务调度等。
有向无环图（DAG图）
有向无环图（Directed Acyclic Graph，简称DAG）是一种没有环的有向图。在DAG中，每个顶点都有一个入度和出度：
- 入度：表示有多少条边指向一个顶点。例如，在下图中，顶点1的入度为0，顶点4的入度为2。
- 出度：表示有多少条边从一个顶点出发。例如，顶点1的出度为2，顶点2的出度为1。
AOV图：顶点活动图
AOV图（Activity On Vertex Network）是在有向无环图的基础上，用顶点表示活动，用边表示活动之间的先后顺序的图结构。例如，下图表示了一个做饭流程的AOV图：
拓扑排序的目的
拓扑排序的目的是在AOV网中找到做事情的先后顺序。例如，在上面的做饭流程图中，有些步骤只有前置步骤完成后才能执行，比如炒菜；有些活动可以直接执行，比如准备厨具和买菜。拓扑排序的结果可能不是唯一的，但必须满足所有活动的先后顺序约束。
拓扑排序的实现
实现拓扑排序的一个重要方法是使用BFS算法。具体步骤如下：
- 找到图中所有入度为0的顶点，将其加入队列。
- 从队列中取出一个顶点，将其加入结果序列。
- 删除与该顶点相连的所有边，更新相关顶点的入度。
- 重复步骤2和3，直到队列为空。
拓扑排序的一个重要应用是判断图中是否有环。如果在拓扑排序过程中发现没有入度为0的顶点，但图中还有剩余顶点，可以判断图中一定存在环形结构。
邻接表的实现
在实现拓扑排序时，需要构建图的邻接表。邻接表是一种常用的数据结构，用于表示图中顶点之间的连接关系。在C++中，可以使用unordered_map<int, vector<int>>或unordered_map<int, unordered_set<int>>来实现邻接表。
例如，对于下面的图：
其邻接表表示为：
unordered_map<int, vector<int>> edges = {
{0, {1, 2}},
{1, {3}},
{2, {3}},
{3, {}}
};
LeetCode题目详解
接下来，我们将通过三个LeetCode题目来深入理解拓扑排序的实现。
207. 课程表
题目描述：判断是否可以完成所有课程的学习，其中某些课程有前置课程的要求。
解题思路
这道题本质上是判断一个有向图中是否存在环。具体步骤如下：
- 根据题目信息构建图的邻接表。
- 使用BFS算法进行拓扑排序。
- 如果所有顶点都能被访问到，说明图中不存在环，返回true；否则返回false。
代码实现
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int>> edges; // 邻接表图
vector<int> in(numCourses); // 保存每个点的入度
queue<int> q;
// 1. 根据题目信息建图
for (auto& e : prerequisites) {
int a = e[0], b = e[1]; // b --> a 的一条边
edges[b].push_back(a);
in[a]++; // 根据下标添加入度
}
// 2. 拓扑排序
// 把入度为0的点扔队列里去
for (int i = 0; i < numCourses; i++)
if (in[i] == 0) q.push(i);
while (q.size()) {
int t = q.front();
q.pop();
// 要把入度为0的点的箭头去掉，其实只要修改下所指向点的入度即可
for (auto e : edges[t]) {
in[e]--; // 减少对应的点的入度
if (in[e] == 0) q.push(e);
}
}
// 3. 判断是否有环
// 只需要判断入度数组还有没有入度不为0的点
for (int i = 0; i < numCourses; i++)
if (in[i] != 0) return false;
return true;
}
};
210. 课程表 II
题目描述：在判断是否可以完成所有课程学习的同时，返回一个可行的学习顺序。
解题思路
这道题与207题类似，只是需要在拓扑排序的过程中记录下结果。具体步骤如下：
- 根据题目信息构建图的邻接表。
- 使用BFS算法进行拓扑排序，并记录下访问顺序。
- 如果所有顶点都能被访问到，返回记录的顺序；否则返回空数组。
代码实现
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int, vector<int>> edges; // 邻接表图
vector<int> in(numCourses); // 保存每个点的入度
queue<int> q;
vector<int> ret;
// 1. 根据题目信息建图
for (auto& e : prerequisites) {
int a = e[0], b = e[1]; // b --> a 的一条边
edges[b].push_back(a);
in[a]++; // 根据下标添加入度
}
// 2. 拓扑排序
// 把入度为0的点扔队列里去
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);
// 要把入度为0的点的箭头去掉，其实只要修改下所指向点的入度即可
for (auto e : edges[t]) {
in[e]--; // 减少对应的点的入度
if (in[e] == 0) q.push(e);
}
}
if (ret.size() == numCourses) return ret;
else return {};
}
};
LCR 144. 火星词典
题目描述：给定一个字符串数组，其中字符串已经按照某种新的字典序进行了排序，要求还原出这种新的字典序。
解题思路
这道题的难点在于理解题意和处理细节。具体步骤如下：
- 通过两层循环遍历字符串数组，使用双指针比较相邻字符串，找出所有需要的顺序关系。
- 构建图的邻接表。
- 使用BFS算法进行拓扑排序，得到字典序。
代码实现
class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> edges; // 邻接表来表示图
unordered_map<char, int> in; // 统计入度
bool check = false; // 处理abc和ab的极端情况
// 1. 初始化入度哈希表
for (auto& e : words)
for (auto ch : e) in[ch] = 0;
// 2. 建图
int n = words.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
add(words[i], words[j]); // add的作用就是把这个对应关系加到 edges 里去，并检测是否出现极端情况
if (check) return "";
}
// 3. 拓扑排序
queue<char> q;
string ret;
for (auto& [a, b] : in)
if (b == 0) q.push(a);
while (q.size()) {
char t = q.front();
q.pop();
ret += t;
for (char e : edges[t]) {
in[e]--;
if (in[e] == 0) q.push(e);
}
}
// 4. 判断是否有环
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)) // 如果a是第一次来是可以存的，或者a已经存过，但是a --> b 的这个信息没有存，也可以存
{
edges[a].insert(b);
in[b]++;
}
break;
}
}
if (i == s2.size() && i < s1.size()) check = true;
}
};
通过以上三个题目，我们可以看到拓扑排序在解决实际问题中的广泛应用。掌握拓扑排序算法，不仅能帮助我们更好地理解图论知识，还能在实际开发中解决许多依赖关系问题。