首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
(判断题)不含回路的有向图一定存在拓扑排序。
[单选题]
(判断题)不含回路的有向图一定存在拓扑排序。
T
F
查看正确选项
添加笔记
求解答(5)
邀请回答
收藏(100)
分享
纠错
4个回答
添加回答
2
青峰啊
首先,拓扑排序是指对于一个
有向无环图
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)
0
犇流
动手画图,前提了解拓扑图,有向图。
发表于 2019-10-06 16:22:44
回复(0)
0
pinkpink*・゜゚
A
发表于 2019-09-12 00:11:45
回复(0)
0
16级老腊肉
百度拓扑排序定义就晓得
发表于 2019-04-13 14:04:59
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
2019
Java工程师
华为
来自:
2019华为网络精英挑...
上传者:
小小
难度:
4条回答
100收藏
3353浏览
热门推荐
相关试题
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(2)
来自
职能类模拟题14
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(3)
来自
职能类模拟题14
(多选题)下面关于传值和传引用说法...
华为
Java工程师
2019
评论
(3)
来自
2019华为网络精英挑战...
(判断题)在shell命令行方式下...
华为
Java工程师
2019
评论
(129)
来自
2019华为网络精英挑战...
(单选题)20个节点的三叉树(每个...
华为
Java工程师
2019
评论
(19)
来自
2019华为网络精英挑战...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题