拓扑排序入门(真的很简单)
2023-09-27 14:29:05 时间
在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。
先统计所有节点的入度,对于入度为0的节点就可以分离出来,然后把这个节点指向的节点的入度减一。
一直做改操作,直到所有的节点都被分离出来。
如果最后不存在入度为0的节点,那就说明有环,不存在拓扑排序,也就是很多题目的无解的情况。
下面是算法的演示过程。
下面是我以前的写法,比较好理解,但是效率低
//b[]为每个点的入度
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(b[j]==0){ //找到一个入度为0的点
ans=j;
vis[cnt++]=j;
b[j]--;
break;
}
}
for(j=1;j<=n;j++)
if(a[ans][j]) b[j]--; //与入度为0的点相连的点的入度减一
}
printf("%d",vis[0]);
for(i=1;i<cnt;i++) printf(" %d",vis[i]);
printf("\n");
下面是我现在一直以来的写法,O(V+E)。点数+边书
queue<int>q;
vector<int>edge[n];
for(int i=0;i<n;i++) //n 节点的总数
if(in[i]==0) q.push(i); //将入度为0的点入队列
vector<int>ans; //ans 为拓扑序列
while(!q.empty())
{
int p=q.front(); q.pop(); // 选一个入度为0的点,出队列
ans.push_back(p);
for(int i=0;i<edge[p].size();i++)
{
int y=edge[p][i];
in[y]--;
if(in[y]==0)
q.push(y);
}
}
if(ans.size()==n)
{
for(int i=0;i<ans.size();i++)
printf( "%d ",ans[i] );
printf("\n");
}
else printf("No Answer!\n"); // ans 中的长度与n不相等,就说明无拓扑序列
有些拓扑排序要求字典序最小什么的,那就把队列换成优先队列就好了。
相关文章
- solr入门之权重排序方法初探之使用edismax改变权重
- [C#]使用 C# 代码实现拓扑排序 dotNet Core WEB程序使用 Nginx反向代理 C#里面获得应用程序的当前路径 关于Nginx设置端口号,在Asp.net 获取不到的,解决办法 .Net程序员 初学Ubuntu ,配置Nignix 夜深了,写了个JQuery的省市区三级级联效果
- 拓扑排序((算法竞赛入门经典)刘汝佳)
- 【华为OD机试真题 python】 运维日志排序【2022 Q4 | 100分】
- c# 集合中有数字、字符的Orderby排序
- 28 MAPREDUCE中的排序初步
- ACM入门之【拓扑排序】
- JS实现拖曳式列表排序
- javascript中sort方法的完整解析--排序
- [模板题][排序]堆排序
- Flutter 修改iOS风格日期选择器CupertinoDatePicker的年月日排序方式
- 使用STL库sort函数对vector进行排序
- 快速排序
- 线性时间排序算法
- 《C#零基础入门之百识百例》(二十三)数组排序 -- 选择排序
- 《C#零基础入门之百识百例》(八十四)系统类List列表类解析 -- 扑克排序
- 高速排序
- 希尔排序算法
- 非递归二叉排序树