浅谈拓扑排序(基于dfs算法)_基于dfs的拓扑排序算法-程序员宅基地

技术标签: DFS  

假设有n个任务,有m个有序对(u,v),表示任务u应该排在任务v之前,那么怎样将这些任务按照顺序排列起来呢?比如有三个有序对(1,4),(3,2),(1,3)排列起来就是1,3,2,4 。尽管还有其他可能(如1,4,3,2),但我们只需找出一种即可,注意:有些情况无法排序,如(1,2),(2,3),(3,1)。

我们把每个任务看成一个点,将每个有序对看成有向边,则形成了一个有向图,由题意可知这个有向图必须是无环的,否则无法排序。在图论中,我们把对这些节点进行排序的问题称为拓扑排序,可借用dfs算法解决该问题。

代码如下:

#include<iostream>
#include<cstring>
using namespace std;
int n,m,topo[100];       //topo数组用来储存最终形成的拓扑序列
int G[100][100];          //储存有序对信息
int c[100];                   //储存每个节点是否被访问过的信息
int t;                          
bool dfs(int u)
{
    c[u]=-1;               //该段代码的一个亮点,表示u节点正在被访问
    for(int v&#

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/langzitan123/article/details/79687736

智能推荐

Material Design控件使用(二)_material design 对接菜单控件 menu.horizontaldisplay-程序员宅基地

文章浏览阅读404次。Material Design控件使用(二)_material design 对接菜单控件 menu.horizontaldisplay

Ubuntu11.04安装完全指南_ubuntu11.04安装qq-程序员宅基地

文章浏览阅读2.2k次。出处:http://apps.hi.baidu.com/share/detail/46047864Ubuntu11.04安装完全指南李顺亮2011年5月3日00:44:09现在的世界变化快,早已不再年少的我们,似乎很难适应ubuntu更新的速度。每半年推出一个新版本,是一路跟进,还是抱残守缺,的确让人有些蛋疼。_ubuntu11.04安装qq

Defy刷魔趣2.3.7包~_跃传app下载-程序员宅基地

文章浏览阅读2.4k次。由于用的defy手机一直都是刚入手的时候装的原生态系统,这么久了,系统垃圾文件太多,用起来非常不爽,今天决定把它做了,据说魔趣的系统做的挺不错,决定换成它了。网上的刷机教程挺多的,但这毕竟是自己第一次刷机,多多少少写点啥纪念一下~话说下面就是所做的步骤了: 1.下载几个包,分别是; (1) http://115.com/file/be2uv75t# 这是_跃传app下载

c语言中a lt b a b是什么意思,C语言中c=a<b?a:b是什么意思-程序员宅基地

文章浏览阅读1.6k次。问: ^ 在C语言中是什么意思?答:这是C语言的逻辑运算符:异或这个网站讲的非常详细,我摘抄了一些,详细的你看以看看。有很例子,好懂!逻辑运算符把各个运算的变量(或常量)连接起来组成一个逻辑表达式。逻辑运算符有4个,它们分别是: !(逻辑非)、 ||(逻辑或)、&&(逻辑与) ^(异或)。在位运算里面还有 &(位与)、|(位或)的运算。 什么是逻辑运算--逻辑运算用来判断一件事情是“对”的还是“错..._c语言中c=a

IE浏览器常见的9个css Bug以及解决办法_在ie9上写css的一些bug-程序员宅基地

文章浏览阅读507次。我们在浏览网页的时候经常看见这样的现象:某个网页在IE6浏览器中打开很正常,但是在IE8里面打开可能完全变形了。或者也有可能出现完全相反的现象。这让Web程序员及设计师往往为了其CSS在各个IE版本下表现怪异而痛苦不已,有时候需要通过专为IE6或者IE8设计单独的定义。IE浏览器则因此被公认为Web程序员的毒药,虽然在微软官网上并没有提供相关的解决方案,但是IE浏览器的兼容性存在的问题却是Web程_在ie9上写css的一些bug

求java用人民币来转换美元,NJUPT JAVA语言 综合图形界面程序设计-程序员宅基地

文章浏览阅读873次。一、实验目的和要求学习和理解JAVASWING中的容器,部件,布局管理器和部件事件处理方法。通过编写和调试程序,掌握JAVA图形界面程序设计的基本方法。实验内容:设计和编写一个用于将人民币转换为等值的美元的程序,界面要求可以输入人民币的金额并可以得到转换后的结果。附:程序使用的人民币外汇牌价参考每100元美元等值买入人民币数:619.72(2015/5/23数据)二、实验代码package..._java jframe做货币转换

随便推点

性能调整相关-程序员宅基地

文章浏览阅读108次。Performance Considerations of Data Types本文大意: 主要介绍数据类型的选择,选择尽量小的数据类型,减少表宽就以为这减少磁盘占用空间,以为这减少读入内存后占用的内存,就以为这减少不必要的cpu来读入数据,处理数据,char和varchar最佳实践小于5使用char大于10使用varchar。关于聚集索引的..._磁盘队列长度很长说明什么

一起学开车救命宝典:遭遇爆胎怎么办?_汽车后轮爆胎如何处理驾校宝典-程序员宅基地

文章浏览阅读901次。遭遇爆胎怎么办?行驶中突然爆胎,这种突发状况对于驾驶员肯定会被弄得措手不及,由于爆胎导致车辆行驶轨迹偏差、操控难度加大会让人想尽快与补救,但对于爆胎事故,很多补救措施往往都是百害而无一利,所以如果在行驶时突然爆胎了,一定不要用下意识的方式去补救,比如急转方向盘、大力刹车都是绝对不能采取的措施!在高速公路上,这样做等于是自杀,因为爆胎后采取这类行为的后果就是100%的失控,甚至翻车。爆胎_汽车后轮爆胎如何处理驾校宝典

Java2HTML改造手记(7)-程序员宅基地

文章浏览阅读227次。<!--google_ad_client = "pub-2947489232296736";/* 728x15, 创建于 08-4-23MSDN */google_ad_slot = "3624277373";google_ad_width = 728;google_ad_height = 15;//--><script type="text/javascript"

组件管理工具Bit_bit js 组件管理-程序员宅基地

文章浏览阅读3.2k次,点赞3次,收藏5次。对比Git你就知道Bit是什么了‘Bit loves Git’对,这是官方文档的原话。Git大家再熟悉不过了,世界上最先进的分布式版本控制系统,没有之一,‘近朱者赤’,大概这就是Bit喜欢Git的原因了。开个玩笑,其实是因为Bit的工作流和Git很相似,也是一个分布式工具。Git是管理源文件、源代码的,Bit也是用来管理代码,但不同的是Git不管你代码的语义结构,而Bit是将代码分..._bit js 组件管理

史上最全的机器学习资料(下)-程序员宅基地

文章浏览阅读165次。推荐:史上最全的机器学习资料(上)机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。机器学习牵涉的编程语言十分之广,包括了MATLAB、Julia、R、P..._stft stms

SpringBoot实战之增删改查_springboot实现增删改查-程序员宅基地

文章浏览阅读6.4w次,点赞13次,收藏189次。首先我们需要使用IDEA新建一个javaweb项目,步骤图示如下选择File菜单中的Project子菜单,弹出如下图所示窗口在右侧菜单中选择Spring Initial,如上图所示选择JDK的版本,此处为JDK1.8。弹出如下如所示的窗口 如上图所示输入包名、选择Maven构建项目,选择java语言,项目打包方式,选择Java JDK的版本,输入项目名称。点击Next弹出..._springboot实现增删改查

推荐文章

热门文章

相关标签