首页 > 试题广场 >

（判断题）不含回路的有向图一定存在拓扑排序。

[单选题]
（判断题）不含回路的有向图一定存在拓扑排序。 
  • T
  • F
查看正确选项
添加回答
青峰啊头像 青峰啊
首先，拓扑排序是指对于一个有向无环图G，将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。那么，假设存在回路，v1,v2,v3,……,vn，v1，则边<v1,v2>∈E(G)，故v1在v2之前，类似地，v2在v3之前，……，因此，得出，v1在vn之前。又因为<vn,v1>∈E(G)，即vn在v1之前。相互矛盾，所以假设不成立。所以，一个图能够进行拓扑排序的一个必要条件就是图中不存在环。
发表于 2019-08-03 14:55:54 回复(0)
犇流头像 犇流

动手画图，前提了解拓扑图，有向图。

发表于 2019-10-06 16:22:44 回复(0)
pinkpink*･゜ﾟ头像 pinkpink*･゜ﾟ
A
发表于 2019-09-12 00:11:45 回复(0)
16级老腊肉头像 16级老腊肉
百度拓扑排序定义就晓得
发表于 2019-04-13 14:04:59 回复(0)
提交观点

问题信息

2019 Java工程师 华为
来自：2019华为网络精英挑...
上传者：小小
难度：
4条回答 3353浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号