广东省建设注册中心网站,设计师互联网,创意网课,互联网创业项目有哪些今天来讲讲拓扑排序 度娘告诉我 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序#xff0c;是将G中所有顶点排成一个线性序列#xff0c;使得图中任意一对顶点u和v#xff0c;若边(u,v)∈E(G)#xff0c;则u在线性序列中出现在v之前。通常#xff0c;这样…今天来讲讲拓扑排序 度娘告诉我 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序是将G中所有顶点排成一个线性序列使得图中任意一对顶点u和v若边(u,v)∈E(G)则u在线性序列中出现在v之前。通常这样的线性序列称为满足拓扑次序(Topological Order)的序列简称拓扑序列。简单的说由某个集合上的一个偏序得到该集合上的一个全序这个操作称之为拓扑排序。 维基百科又和我说 在图论中由一个有向无环图的顶点组成的序列当且仅当满足下列条件时称为该图的一个拓扑排序英语Topological sorting。 每个顶点出现且只出现一次若A在序列中排在B的前面则在图中不存在从B到A的路径。也可以定义为拓扑排序是对有向无环图的顶点的一种排序它使得如果存在一条从顶点A到顶点B的路径那么在排序中B出现在A的后面[1]。 想了解的自己去找我就说这么多了。 下面步入正题。 看下面的样例。 不过要先说明一下输入格式第一行一个整数N之后的N行每行若干个以0为结尾的整数。 表示第 i 个节点向这些个节点都有一条有向边。 那么这张图的拓扑排序就是2 4 5 3 1当然可能并不唯一。 下图是他拓扑排序后变得更加直观的图 那么这个拓扑排序是如何实现的呢。 下面我们就来看看。 首先定义一个indgr数组表示每个点的入度就是有几条边是指向他的。 定义一个栈。先将所有入度为0的点入栈。然后每次都把栈顶元素输出并且弹出记录下来还要用一个cnt记录输出次数。输出之后把与相连的点的入度-1如果-1之后这个点的入度变为了0那么就将这个点入栈重复此操作直到所有的点都被输出一遍也就是说cntn的时候就可以结束程序了。 下面是代码 #include iostream
#include cstdio
#include cstring
#include stackusing namespace std;stackint S;
int n, cnt;
int son, tot[105];
int indgr[108];
int ed[105][105];int main() {scanf(%d, n);for(int i1; in; i) {while(scanf(%d, son) 1) {if(son 0) {break;}ed[i][tot[i]] son;indgr[son];}}for(int i1; in; i) {if(indgr[i] 0) {S.push(i);}}while(cnt ! n) {int k S.top();printf(%d , k);cnt;S.pop();for(int i1; itot[k]; i) {indgr[ed[k][i]]--;if(indgr[ed[k][i]] 0) {S.push(ed[k][i]);}}}return 0;
} 作者wlz 出处http://www.cnblogs.com/bljfy/p/8729163.html 本文版权归作者和博客园共有欢迎转载但未经作者同意必须保留此段声明且在文章页面明显位置给出原文连接否则保留追究法律责任的权利。转载于:https://www.cnblogs.com/bljfy/p/8729163.html
