有向无环图拓扑排序 有环法

来源：蜘蛛抓取(WebSpider) 时间：2017-12-04 05:27 标签： 拓扑排序判断环
有向无环图拓扑排序找最短路径的问题（已解决） - 『编程语言讨论求助区』
- 吾爱破解 - LCG - LSG |安卓破解|病毒分析|破解软件|
后使用快捷导航没有帐号？
只需一步，快速开始
请完成以下验证码
请完成以下验证码
查看: 867|回复: 4
有向无环图拓扑排序找最短路径的问题（已解决）
阅读权限10
发帖求助前要善用【】功能，那里可能会有你要找的答案；
求助软件脱壳或者破解思路时，请务必在主题帖中描述清楚你的分析思路与方法，否则会当作求脱求破处理；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类改成【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人。
本帖最后由 葬礼昨天 于
22:14 编辑
谁能解释下为什么R节点是无穷
(7.77 KB, 下载次数: 2)
21:56 上传
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限10
表示看不懂。。。
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限10
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限10
楼主，怎么解决的能说下吗
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限10
楼主，怎么解决的能说下吗
那是规定。。。。
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
免责声明：吾爱破解所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。本站信息来自网络，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，购买注册，得到更好的正版服务。
( 京ICP备号 | 京公网安备 87号 )
Powered by Discuz!
Comsenz Inc.一堆理论，空话连篇 看例子： 假设 1 2 3
4是某个图唯一的拓扑排序序列，来看看它能满足哪些图！ 1-2 2-3 3-4
1-2 2-4 3-4 2-3
1-2 2-4 3-4 2-3
可以吧！ 三个图都满足唯一拓扑排序1 2
3 4 请问？ 你让我如何确定是哪个图！
对有向图a,b,c,d
,边&a,b&，&b,c&，&c,d&，&a,c&，拓扑序列唯一为a，b，c，d。如果去掉边&a,c&，拓扑序列还是唯一的a，b，c，d。故拓扑序列唯一不能唯一确定有向图。
看了基本思路，再理解楼上的例子会更好吧。
对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。
拓扑排序无法反推图，但是若存在u到v的路径，拓扑序列中u一定出现在v的前边
书上的答案是：X
如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
但是我写得时候也觉得答案有问题啊！
不过看了楼上“先要说明一下什么情况下有向无环图的拓扑序列才会唯一”以及“拓展到拓扑排序中，结果具有唯一性的条件也是其所有顶点之间都具有全序关系。如果没有这一层全序关系，那么拓扑排序的结果也就不是唯一的了。”答案也是可以合理解释的。
结点间的顺序可确定，但是结点之间的边连接不能完全确定。
不是 很简单的一个反例
三个顶点 1,2,3
两条边 1-&3,2-&3
1，2，3跟2,1,3都是合法的拓扑排序
先要说明一下什么情况下有向无环图的拓扑序列才会唯一
先来看看求拓扑序列的过程，每次寻找入度为0的点，并在图中将该点删除。
所以若拓扑序列唯一，则每一次操作过后，图中有且仅有一个节点的入度为0
所以若有唯一的拓扑序列x1,x2......xn
则有向图仅能够是x1-&x2,x2-&x3.....x(n-1)-&xn
这道题你会答吗？花几分钟告诉大家答案吧！
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
浙ICP备号-2
扫一扫，把题目装进口袋一个有向无环图的拓扑排序序列是唯一的么_百度知道
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。
一个有向无环图的拓扑排序序列是唯一的么
我有更好的答案
一般不唯一，如果同时有多个如果为0的顶点供选择时，不会唯一
为您推荐：
其他类似问题
拓扑排序的相关知识
换一换
回答问题，赢新手礼包

我要回帖

更多关于 拓扑排序判断环 的文章

 

随机推荐