首页 > 代码库 > 拓扑序列以及排序
拓扑序列以及排序
一句话题意：求AOV网的拓扑序列，输出按字典序最小的一个。
拓扑排序 ：
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。 （摘自 ： 百度百科）
方案一，用邻接矩阵来储存图，时间复杂度为 O（n * n），因为代码简单就不贴出来了。
方案二，用优先队列以及前向星来储存时间复杂度为 O（n+e）
证明过程：n顶点e条弧向图言建立求各顶点入度间复杂度O(e)；建零入度顶点栈间复杂度O(n)；拓扑排序程若向图环则每顶点进栈、栈入度减1操作while语句总共执行e所总间复杂度O(n+e)
我在代码中还加了运算符重载，struct cmp函数其实等同于greater,不会用也没有关系
#include<bits/stdc++.h>using namespace std;struct Edge{ int to,next,w;};struct Edge edge[20000];int book[2000];int n,m;int head[2000];int cnt=0;void add(int x,int y){ book[y]++;//表示入度 edge[++cnt].to=y; edge[cnt].next =head[x]; head[x]=cnt;}struct cmp{ bool operator () (const int a,const int b )const { return a>b; }};void toposort(int n){ priority_queue <int ,vector <int>, cmp> que; for(int i=1;i<=n;i++) if(book[i]==0) { book[i]--; que.push(i); } int k=1; while(!que.empty()) { int u=que.top();que.pop(); char str; str=((k++!=n)?‘ ‘:‘\n‘);//逗比到不行的判断是否在文末的方法 cout<<u<<str; for(int i=head[u];i;i=edge[i].next) { int j=edge[i].to; book[j]--; if(book[j]==0) que.push(j); } }}int main(){ int x,y; cin>>n>>m; while(m--) { cin>>x>>y; int ok=0; for(int i=head[x];i;i=edge[i].next) if(edge[i].to==y) {ok=1;break; } //判断重边 if(!ok) add(x,y); } toposort(n);//n个点 return 0;}
拓扑序列以及排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。