首页 > 代码库 > 拓扑排序 topsort详解
拓扑排序 topsort详解
1.定义
对一个有向无环图G进行拓扑排序,是将G中所有顶点排成一个线性序列,通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
举例:
<style>h3 { margin-top: 0.46cm; margin-bottom: 0.46cm; direction: ltr; color: #000000; line-height: 172%; text-align: justify; page-break-inside: avoid; orphans: 0; widows: 0 } h3.western { font-family: "Calibri", "Lucida Sans Unicode", sans-serif; font-size: 16pt } h3.cjk { font-family: "宋体"; font-size: 16pt } h3.ctl { font-family: "Times New Roman", serif; font-size: 12pt; font-weight: normal } p { margin-bottom: 0.25cm; direction: ltr; color: #000000; line-height: 120%; text-align: justify; orphans: 0; widows: 0 } p.western { font-family: "Calibri", "Lucida Sans Unicode", sans-serif; font-size: 10pt } p.cjk { font-family: "宋体"; font-size: 10pt } p.ctl { font-family: "Times New Roman", serif; font-size: 12pt } a:link { }</style>我们起床穿裤子和鞋子时,相信大部分人的顺序是这样的,先穿上内裤,然后再穿上裤子,再穿上袜子,然后才是鞋子。那么,我们把这些步骤分解:
(1)穿内裤
(2)穿裤子
(3)穿袜子
(4)穿鞋子
我们把这四个步骤,按照上述的顺序给排一下,就是所谓的拓扑排序 。
2.注意
1)只有有向无环图才存在拓扑序列;
2)对于一个DAG,可能存在多个拓扑序列;
如:
该DAG的拓扑序列为A B C D或者A C B D
而此有向图是不存在拓扑序列的,因为图中存在环路
3..拓扑序列算法思想
(1)从有向图中选取一个没有前驱(即入度为0)的顶点,并输出之;
(2)从有向图中删去此顶点以及所有以它为尾的弧;
重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。
4.代码
#include<cstdio> #include<cstring> int ans[510][510];//记录两人是否进行了比赛 int n,indegree[510];//记录前驱个数 int queue[510];//保存拓扑 void topsort() { int i,j,top,k=0; for(j=0; j<n; ++j) { for(i=1; i<=n; ++i) { if(indegree[i]==0)//前驱为零即是当前第一名 { top=i; break; } } queue[k++]=top;//当前第一名入队列,也可以直接输出 indegree[top]=-1;//前驱数量更新为-1,避免重复入队列 for(i=1; i<=n; ++i) { if(ans[top][i])//将前驱中含有当前第一名的前去数量减一 indegree[i]--; } } for(i=0; i<k-1; ++i) printf("%d ",queue[i]); printf("%d\n",queue[n-1]); } int main() { int i,a,b,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(indegree,0,sizeof(indegree));//数组初始化为0 memset(ans,0,sizeof(ans));//数组初始化为0 for(i=0; i<m; ++i) { scanf("%d%d",&a,&b); if(ans[a][b]==0) { ans[a][b]=1;//记录是否进行了比赛 indegree[b]++;//记录前驱数量 } } topsort(); } return 0; }
拓扑排序 topsort详解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。