图的拓扑排序

图的拓扑排序

图的拓扑排序是针对有向无环图而言的，对于有向无环图G（环，是指一点经有向路径能回到原点），拓扑排序是把G中所有的顶点排列成一个线性序列，使得任意一对顶点u,v，若存在边，则u在v之前出现。用这种方式产生的序列称之为拓扑序列。一个有向无环图可能有很多的拓扑序列。

无前驱的顶点优先拓扑排序算法：

（1）从有向图中选择入度为0的顶点并输出它；

（2）删除这个顶点，并且删除由这个顶点发出的所有的有向边。

（3）重复上述步骤，直到删除所有的顶点。

注意：在数据输入的时候就应该统计每个顶点的入度，删除一个顶点后也应该马上更新其他受影响的点的入度。所以应该再开一个额外的数组indegree[].

例子：

输入数据：

8 10 2 4 1 1 2 2 1 3 3 4 6 4 5 7 5 3 5 6 7 8 7 6 8 8 3 6 9 6 7 10

#include #includeusing namespace std;const int maxn=101; int head[maxn],indegree[maxn],n,m; struct node{ int to,w,next; }edge[maxn]; void topsort(){ int que[maxn],iq=0,i,k; for(i=1;i<=n;i++)if(indegree[i]==0)que[iq++]=i; for(i=0;i0;k=edge[k].next){ indegree[edge[k].to]--; if(indegree[edge[k].to]==0)que[iq++]=edge[k].to; } } for(i=0;i>n>>m; for(i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); edge[i].to=b; edge[i].w=c; edge[i].next=head[a]; head[a]=i; indegree[b]++; } topsort(); return 0;}

输出结果：

1 3 2 5 4 6 7 8

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。