回答以下关于图的问题：对于一个有向图，不用拓扑排序，如何判断图中是否存在环?

admin2014-10-20 80

问题回答以下关于图的问题：
对于一个有向图，不用拓扑排序，如何判断图中是否存在环?

选项

答案对于有向图进行深度优先遍历。如果从有向图上某个顶点v出发遍历，DFS(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v到顶点u的环。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/w0vR777K

本试题收录于：计算机科学与技术题库普高专升本分类

计算机科学与技术

普高专升本

相关试题推荐

阵发性室上性心动过速的心电图特点是()。
如图所示，已知钢板厚度t=10mm，其抗剪强度[τ]=300MPa。若用冲床将钢板冲出直径d=32mm的孔，则需要的冲剪力F=__________。
在跨度、荷载不变的条件下，控制三铰拱水平反力的唯一参数是矢高。()
在探索中国社会主义建设道路的过程中，毛泽东指出社会主义社会可能分为()
下列哪一项不是肺的生理功能所主?()
表里的病势出入，实际上取决于：
蛋白质元素组成的特点是含有的16％相对恒定置的是什么元素
刺激心迷走神经，下述哪项结果不正确()
模板DNA的碱基序列是3’一LTGCAGT-5’，其转录出RNA碱基序列是：()
8086CPU由EU和BIU两大部件组成：前者主要负责执行指令，后者_______。

随机试题

钻床可采用220V照明灯具。（）
法律和道德都具有规范社会行为、调节社会关系、维护社会秩序的作用，在国家治理中都有其地位和功能。两者的关系是()
患者，女，50岁。在家燃煤取暖突然昏迷，出现面色潮红，口唇呈樱桃红色，多汗，神志不清伴发热。确诊的检查是
犯罪嫌疑人刘某涉嫌故意杀人被公安机关立案侦查。在侦查过程中，侦查人员发现刘某行为异常。经鉴定，刘某属于依法不负刑事责任的精神病人，需要对其实施强制医疗。(2012年试卷二第95～96题)关于有权启动强制医疗程序的主体，下列选项正确的是：
关于房地产投资利弊的说法，错误的是()。
简述学生心理发展的基本特征。
我常常会感到很多字和词被造出来其实是一种浪费，因为所用极少，要么束之高阁英雄无用武之地，要么养尊处优一笔一画脂肪成堆；而其他一些字词则呈现出紧张，无数的含义引申义统统压在它身上，似乎让那个汉字不堪重负快要喊出声来。这是字义资源分配的不对称。这段文字
软件复用是使用已有的软件产品(如设计、代码、文档等)来开发新的软件系统的过程。软件复用的形式大体可分为垂直式复用和水平式复用。垂直式复用是指(66)中的复用，水平式复用是指(67)中的复用。为了提高构件的复用率，通常要求构件具有较好的(68)。为了将不同软
请在【答题】菜单下选择【进入考生文件夹】命令，并按照题目要求完成下面的操作。注意：以下的文件必须保存在考生文件夹下。文慧是新东方学校的人力资源培训讲师，负责对新人职的教师进行人职培训，其PowerPoint演示文稿的制作水平广受好评。最
Whohasauthorizedtheweatherbulletin?

最新回复(0)

回答以下关于图的问题： 对于一个有向图，不用拓扑排序，如何判断图中是否存在环?

计算机科学与技术

普高专升本

阵发性室上性心动过速的心电图特点是()。

如图所示，已知钢板厚度t=10mm，其抗剪强度[τ]=300MPa。若用冲床将钢板冲出直径d=32mm的孔，则需要的冲剪力F=__________。

在跨度、荷载不变的条件下，控制三铰拱水平反力的唯一参数是矢高。()

在探索中国社会主义建设道路的过程中，毛泽东指出社会主义社会可能分为()

下列哪一项不是肺的生理功能所主?()

表里的病势出入，实际上取决于：

蛋白质元素组成的特点是含有的16％相对恒定置的是什么元素

刺激心迷走神经，下述哪项结果不正确()

模板DNA的碱基序列是3’一LTGCAGT-5’，其转录出RNA碱基序列是：()

8086CPU由EU和BIU两大部件组成：前者主要负责执行指令，后者_______。

钻床可采用220V照明灯具。（）

法律和道德都具有规范社会行为、调节社会关系、维护社会秩序的作用，在国家治理中都有其地位和功能。两者的关系是()

患者，女，50岁。在家燃煤取暖突然昏迷，出现面色潮红，口唇呈樱桃红色，多汗，神志不清伴发热。确诊的检查是

关于房地产投资利弊的说法，错误的是()。

简述学生心理发展的基本特征。

Whohasauthorizedtheweatherbulletin?

回答以下关于图的问题：对于一个有向图，不用拓扑排序，如何判断图中是否存在环?