拓扑排序
2026-09-06 15:09:22
发布于：浙江
由于帖主是全校最菜，所以，这篇，只讲，简单的，原理与实现过程，dfs的方法我看不懂但是会放出来。
大家肯定对图论有一些了解，此篇只会用到 环、有向图、出入边 这几个内容。
正题
啥是拓扑排序
假如你要学习 Dijkstra 算法与 BFS ，那么你首先要会使用 priority_queue ，但这之前你要先会用 queue 这就是一个类似于前缀后缀关系的图（?），每次的 “会使用”就代表一条有向边，大概就是
这样的关系。
但是，如果我们要先学 queue 才能学 priority_queue ，但想学会 queue 还要先会 priority_queue ，该怎么办呢？这显然出现了一个环，我们也不知道该怎么进行学习（同时学除外）。
今天的主题拓扑排序，就是基于上面的图来的。
拓扑排序就是通过特定的规则使图里排在前面的点都能到排在它后面的点，所以这个拓扑排序也是不唯一的。
思想是啥？
每次取现入度为 的点，再删掉这个点与它所有的出度，那么会形成新的图，再一直重复这个过程直到一个点都不剩，那这个就要用到 queue 了，我们的 queue 里存放的就是每个入度为 的点，那么这个重复的过程显然就是 while(!q.empty()) 。
一开始我们的 queue 放啥？
当然是一开始入度就为 的点，所以我们还要有个数组来记录入度，在最开始的时候遍历 for(int i = 1;i<=n;i++) if(in[i]==0) q.push(i) 。
如何存图？
这啥问题，用 vector 存节点与后缀（就是这个点能到的那些点）即可。
讲环干嘛啊？
为啥讲那个 pq 和 queue 的例子呢，就是说我们的拓扑排序只适合在 DAG 、AOV网、AOE网里使用（因为有环删不完所有的点），感兴趣的同学可以查查看。
实现
借助例题吧。
这道题还是很人性的，在排序的时候只要每拿出一个点输出一下就可以了。
int main()
{
int n, in[105]={};//in存入度
vector<int> g[105];
queue<int> q;
cin>>n;
for(int i = 1;i<=n;i++)
{
int a;
while(cin>>a&&a!=0)
{
g[i].push_back(a);
in[a]++;//入度加一代表i能到a
}
}
for(int i = 1;i<=n;i++) if(in[i]==0) q.push(i);//存起点
while(!q.empty())
{
int u=q.front();
q.pop();//记得pop掉不然T飞你
cout<<u<<" ";
for(auto v:g[u]) if(--in[v]==0) q.push(v);//--in[v]可以直接用减好的
}
}
为啥要--in[v]？
因为要删边的话对应的入度也会减 ，所以只要现在是 ，也就是在 时就可以加入队列，当然不要忘记把这个边给删掉。
说人话就是，给你一些前后缀关系，你需要判断什么时候能出现唯一的拓扑排序，然后还有一些判断（不唯一和有环），那我们写一个函数即可（因为还要输出这个拓扑序结果），每次拿队头的元素，注意这里要一个 来标记，每次如果出现 个以上的入度为 的元素就说明拓扑序不唯一，然后就是重复排序过程，但这里要在答案字符串里加上每个队头元素作为我们的拓扑序结果，最后判断答案字符串是不是包含了所有元素，不是则有环。
vector<char> g[30];
int n, m, in[35];
int toposort(string &res)
{
int ind[35];
memcpy(ind,in,sizeof ind);//这个就是复制数组内容，在cstring里
queue<int> q;
res="";//答案字符串
for(int i = 0;i<n;i++) if(ind[i]==0) q.push(i);
bool f=0;
while(!q.empty())
{
if(q.size()>1) f=1;//判唯一性
int u=q.front();
q.pop();
res+=char('A'+u);//由于存进去是int,所以出来要加上我们减掉的A
for(auto v:g[u])
{
if(--ind[v]==0) q.push(v);
}
}
if(res.size()<n) return 2;//有环
if(f==1) return 0;//不唯一
return 1;
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
char a, x, b;
cin>>a>>x>>b;
g[a-'A'].push_back(b-'A');//保证下标是整数
in[b-'A']++;//同理
string ans;//答案字符串
int op=toposort(ans);//注意这里ans被改变，里面是真正的答案，但返回值为0/1/2
if(op==1)//已经有唯一拓扑序
{
//输出这个ans作为答案即可
cout<<"Sorted sequence determined after "<<i<<" relations: "<<ans<<".";
return 0;
}
if(op==2)//有环
{
cout<<"Inconsistency found after "<<i<<" relations.";
return 0;
}
}
cout<<"Sorted sequence cannot be determined.";//不唯一要最后输出
}
DFS实现
using Graph = vector<vector<int>>; // 邻接表
struct TopoSort {
enum class Status : uint8_t { to_visit, visiting, visited };
const Graph& graph;
const int n;
vector<Status> status;
vector<int> order;
vector<int>::reverse_iterator it;
TopoSort(const Graph& graph)
: graph(graph),
n(graph.size()),
status(n, Status::to_visit),
order(n),
it(order.rbegin()) {}
bool sort() {
for (int i = 0; i < n; ++i) {
if (status[i] == Status::to_visit && !dfs(i)) return false;
}
return true;
}
bool dfs(const int u) {
status[u] = Status::visiting;
for (const int v : graph[u]) {
if (status[v] == Status::visiting) return false;
if (status[v] == Status::to_visit && !dfs(v)) return false;
}
status[u] = Status::visited;
*it++ = u;
return true;
}
};
看不懂，谁来给我讲下？
@Eucatastrophe🐛 您太强了，修正了一处错误，%%%。
全部评论 4
但是，如果我们要先学 queue 才能学 priority_queue ，但想学会 priority_queue 还要先会 queue ，该怎么办呢？这显然出现了一个环，我们也不知道该怎么进行学习（同时学除外）。
这不是个单向边吗
2026-09-06 来自 浙江
0
有帮助，赞一个