条件：
1.每个顶点出现且只出现一次。
2.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图(DAG)才有拓扑排序，非DAG图没有拓扑排序一说。
一般用有向边指示顺序关系，运用于顺序关系。
例如，下面这个图：
显然是一个DAG图，1→4表示4的入度+1，4是1的邻接点,
代码表示：前者deg[4]++;后者用vector[1].push(4)
如何写出拓扑排序代码？
1.首先将边与边的关系确定，建立好入度表和邻接表。
2.从入度为0的点开始删除，如上图显然是1的入度为0，先删除。
3.于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。通常，一个有向无环图可以有一个或多个拓扑排序序列。因为同一入度级别的点可以有不同的排序方式。
4.拓扑排序可以判断图中有无环，如下图
显然4，5，6入度都是1，不存在入度为0的点，无法进行删除操作。判断有无环的方法，对入度数组遍历，如果有的点入度不为0，则表明有环。
例题+代码
拓扑排序(一)-Hiho-Coder1174
描述
由于今天上课的老师讲的特别无聊，小Hi和小Ho偷偷地聊了起来。
小Ho：小Hi，你这学期有选什么课么？
小Hi：挺多的，比如XXX1,XXX2还有XXX3。本来想选YYY2的，但是好像没有先选过YYY1，不能选YYY2。
小Ho：先修课程真是个麻烦的东西呢。
小Hi：没错呢。好多课程都有先修课程，每次选课之前都得先查查有没有先修。教务公布的先修课程记录都是好多年前的，不但有重复的信息，好像很多都不正确了。
小Ho：课程太多了，教务也没法整理吧。他们也没法一个一个确认有没有写错。
小Hi：这不正是轮到小Ho你出马的时候了么！
小Ho：哎？？
我们都知道大学的课程是可以自己选择的，每一个学期可以自由选择打算学习的课程。唯一限制我们选课是一些课程之间的顺序关系：有的难度很大的课程可能会有一些前置课程的要求。比如课程A是课程B的前置课程，则要求先学习完A课程，才可以选择B课程。大学的教务收集了所有课程的顺序关系，但由于系统故障，可能有一些信息出现了错误。现在小Ho把信息都告诉你，请你帮小Ho判断一下这些信息是否有误。错误的信息主要是指出现了"课程A是课程B的前置课程，同时课程B也是课程A的前置课程"这样的情况。当然"课程A是课程B的前置课程，课程B是课程C的前置课程，课程C是课程A的前置课程"这类也是错误的。
输入
第1行：1个整数T，表示数据的组数T(1 <= T <= 5)
接下来T组数据按照以下格式：
第1行：2个整数，N,M。N表示课程总数量，课程编号为1..N。M表示顺序关系的数量。1 <= N <= 100,000. 1 <= M <= 500,000
第2..M+1行：每行2个整数，A,B。表示课程A是课程B的前置课程。
输出
第1..T行：每行1个字符串，若该组信息无误，输出"Correct"，若该组信息有误，输出"Wrong"。
Sample Input
2
2 2
1 2
2 1
3 2
1 2
1 3
Sample Output
Wrong
Correct
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxa=;
vectorvec[maxa];
queueq;
int rudu[maxa];
int t,n,m,x,y,now;
bool tuopu(){
int cnt=;
while(!q.empty()) q.pop();
for(int i=;i<=n;i++)
if(rudu[i]==) q.push(i);
while(!q.empty()){
now=q.front();
cnt++;
q.pop();
for(size_t i=;i
if(--rudu[vec[now][i]]==)
q.push(vec[now][i]);
}
if(cnt==n) return true;
else return false;
}
int main(){
cin>>t;
while(t--)
{
cin>>n>>m;
memset(rudu,,sizeof(rudu));
for(int i=;i<=n;i++) vec[i].clear();
while(m--)
{
cin>>x>>y;
vec[x].push_back(y);
rudu[y]++;//入度+1
}
if(tuopu()) cout<
else cout<
}
return ;
}
C#实现有向无环图(DAG)拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在 ...
判断有向无环图(DAG)
1.拓扑排序 bfs 所有入度为0的先入选. 2.tarjan 1个点1个集合 3.暴力 一个点不能重新到达自己
【模板整合计划】图论—有向无环图 (DAG) 与树
[模板整合计划]图论-有向无环图 (DAG) 与树 一:[拓扑排序] 最大食物链计数 \(\text{[P4017]}\) #include #include
【拓扑】【宽搜】CSU 1084 有向无环图 (湖南省第十二届大学生计算机程序设计竞赛)
题目链接: http://acm./OnlineJudge/problem.php?id=1804 题目大意: 一个有向无环图(DAG),有N个点M条有向边(N,M<=105 ...
javascript实现有向无环图中任意两点最短路径的dijistra算法
有向无环图 一个无环的有向图称做有向无环图(directed acycline praph).简称DAG 图.DAG 图是一类较有向树更一般的特殊有向图, dijistra算法 摘自 http://w ...
有向无环图的应用—AOV网 和 拓扑排序
有向无环图:无环的有向图,简称 DAG (Directed Acycline Graph) 图. 一个有向图的生成树是一个有向树,一个非连通有向图的若干强连通分量生成若干有向树,这些有向数形成生成森林 ...
图->;有向无环图->;拓扑排序
文字描述 关于有向无环图的基础定义: 一个无环的有向图称为有向无环图,简称DAG图(directed acycline graph).DAG图是一类较有向树更一般的特殊有向图. 举个例子说明有向无环图 ...
CSU 1804: 有向无环图 拓扑排序 图论
1804: 有向无环图 Submit PageSummaryTime Limit:5 SecMemory Limit:128 MbSubmitted:716 ...
第十二届湖南省赛 (B - 有向无环图 )(拓扑排序+思维)好题
Bobo 有一个 n 个点,m 条边的有向无环图(即对于任意点 v,不存在从点 v 开始.点 v 结束的路径). 为了方便,点用 1,2,…,n 编号. 设 count(x,y) 表示点 x 到点 y ...
随机推荐
Jsp 错题分析
ArrayList删除元素通过RemoveAt(int index)来删除指定索引值的元素 运行时异常都是RuntimeException类及其子类异常,如NullPointerException.I ...
python框架(flask/django/tornado)比较
一.对外数据接口 三者作为web框架,都是通过url映射对外的接口 flask:以decorator的形式,映射到函数中 django:以字典形式,映射到函数 tornado: 以字典形式,映射到类中 ...
WPF 基础到企业应用系列索引
转自:/zenghongliang/archive//07/09/1774141.html WPF 基础到企业应用系列索引 WPF 基础到企业应用系 ...
(medium)LeetCode 207.Course Schedule
There are a total ofncourses you have to take, labeled from0ton - 1. Some courses may have prer ...
配置Nginx服务
一,安装之前准备1.nginx依赖: gcc openssl-devel pcre-devel zlib-devel 安装依赖:yum install gcc openssl-devel pcr ...
javascript语言学习笔记。
js类创建方法 var DogKing = function(dogName){ this.dogName = dogName; }; var myDogKing = new DogKing(&quo ...
bzoj 2212: [Poi]Tree Rotations
Description Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some in ...
《深入理解Java虚拟机》-----第8章 虚拟机字节码执行引擎——Java高级开发必须懂的
概述 执行引擎是Java虚拟机最核心的组成部分之一.“虚拟机”是一个相对于“物理机”的概念 ,这两种机器都有代码执行能力,其区别是物理机的执行引擎是直接建立在处理器.硬件.指令集和操作系统层面上的,而 ...
APICloud Studio2新建应用报错和检出错误
今天心血来潮,闲暇时间想做个移动应用app,听一哥们说APICloud开发app很方便,就查询了一下,看了之后简直就是热血沸腾,我感觉正是我一直要找的工具 信心满满的开始着手使用,看了一下介绍我选择了 ...
