算法学习之路|拓扑排序
摘要： 拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。（来自百度百科定义）
如果你学过离散数学就不难理解这定义，如果没学过可能就没法理解，建议先去补补偏序/全序的概念，本篇不会多谈这些理论概念性的东西，想要了解请自行百度。
接下来说下拓扑排序的算法实现：
拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
废话不多说上代码(用的是c++stl实现的)
vector G[MAXN];// 邻接表。 intson[MAXN];// 入度数。 voidtopo(){queue que;intok =0;for(inti =0; i < n; i++)if(!son[i]) que.push(i);// 入度为0时入队。 while(!que.empty()){if(que.size() >1) ok =1;// 当队列中个数超多1时，表示有不唯一解。 intt = que.front(); que.pop(); cnt--;// 如果队列为空后，计数器> 0， 说明存在环结构。 for(inti =0; i < G[t].size(); i++)if(--son[G[t][i]] ==0)// 判断减掉当前点的关系后，点的入度是否为0。 que.push(G[t][i]); } }
代码参考：https://www.2cto.com/kf/201308/233520.html
版权声明：本文内容由互联网用户自发贡献，版权归作者所有，本社区不拥有所有权，也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至：yqgroup@service.aliyun.com 进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。
用云栖社区APP，舒服~
