专栏文章

拓扑排序

算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mina9ag4
此快照首次捕获于
2025/12/01 23:07
3 个月前
此快照最后确认于
2025/12/01 23:07
3 个月前
查看原文

定义

拓扑排序 (Topological(Topological sorting)sorting) 要解决的问题是如何给一个有向无环图的所有节点排序。

Kahn 算法

过程

初始状态下,集合 SS 装着所有入度为 00 的点,LL 是一个空列表。每次从 SS 中取出一个点 uu (可以随便取)放入 LL^` 然后将 uu 的所有边 (u,v1),(u,v2),(u,v3)(u, v_1), (u, v_2), (u, v_3) \cdots 删除。对于边 (u,v)(u, v), 若将该边删除后点 vv 的入度变为 00,则将 vv 放入 SS 中。
不断重复以上过程,直到集合 SS 为空。检查图中是否存在任何边,如果有,那么这个图一定有环路,否则返回 LLLL 中顶点的顺序就是构造拓扑序列的结果。

时间复杂度

假设这个图 G=(V,E)G = (V, E) 在初始化入度为 00 的集合 SS 的时候就需要遍历整个图,并检查每一条边,因而有O(E+V)O(E+V) 的复杂度。然后对该集合进行操作,显然也是需要 O(E+V)O(E+V) 的时间复杂度。
因而总的时间复杂度就有 𝑂(𝐸+𝑉)𝑂(𝐸 +𝑉)

例题

codemycode_{my}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 条评论,欢迎与作者交流。

正在加载评论...