专栏文章
拓扑排序
算法·理论参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mina9ag4
- 此快照首次捕获于
- 2025/12/01 23:07 3 个月前
- 此快照最后确认于
- 2025/12/01 23:07 3 个月前
定义
拓扑排序 要解决的问题是如何给一个有向无环图的所有节点排序。
Kahn 算法
过程
初始状态下,集合 装着所有入度为 的点, 是一个空列表。每次从 中取出一个点 (可以随便取)放入 然后将 的所有边 删除。对于边 , 若将该边删除后点 的入度变为 ,则将 放入 中。
不断重复以上过程,直到集合 为空。检查图中是否存在任何边,如果有,那么这个图一定有环路,否则返回 , 中顶点的顺序就是构造拓扑序列的结果。
时间复杂度
假设这个图 在初始化入度为 的集合 的时候就需要遍历整个图,并检查每一条边,因而有 的复杂度。然后对该集合进行操作,显然也是需要 的时间复杂度。
因而总的时间复杂度就有
例题
CPP
#include <bits/stdc++.h>
using namespace std;
int n,a[10004],into[10004],t,vis[10004];
vector<int>edge[10004];
queue<int>q;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
while(cin>>t)
{
if(t==0)break;
edge[i].push_back(t);
into[t]++;
}
}
for(int i=1;i<=n;i++)
if(into[i]==0&&!vis[i])q.push(i),vis[i]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
cout<<u<<" ";
for(int i=0;i<edge[u].size();i++)
into[edge[u][i]]--;
for(int i=1;i<=n;i++)
if(into[i]==0&&!vis[i])q.push(i),vis[i]=1;
}
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...