首页
登录
公务员类
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
免费题库
2022-08-02
56
问题
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求关键路径的方法B.求最短路径的Dijkstra方法C.广度优先遍历算法D.深入度优先遍历算法
选项
A.求关键路径的方法
B.求最短路径的Dijkstra方法
C.广度优先遍历算法
D.深入度优先遍历算法
答案
D
解析
判断一个图是否存在回路的方法包括:(1)设图G是n个顶点的无向图,若G的边数e>=n,则图G中一定有回路存在。(2)设图G是n个顶点的无向连通图,若G的每个顶点的度>=2,则图G中一定有回路存在。(3)利用拓扑排序算法可以判断图中是否存在回路。即在拓扑排序输出结束后所余下的顶点均有前驱,则说明只得到了部分顶点的拓扑有序序列,图中存在有回路。(4)利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来说,若深度优先遍历过程中遇到了回边则必定存在环;对于有向图来说,这条回边可能是指向深度优先森林中另一棵生成树上顶点的弧;但是,如果从有向图上的某个项点v出发进行深度优先遍历,若在dfs(v)结束之前出现一条认顶点v到顶点v的回边,因u在生成树上是v的孙子,则有向图必定存在半含顶点u和顶点v的环。
转载请注明原文地址:https://tihaiku.com/gongwuyuan/2555166.html
本试题收录于:
计算机 电网题库国家电网招聘分类
计算机 电网
国家电网招聘
相关试题推荐
在短期借款的利息计算和偿还方法中,企业实际利率高于报价利率的有()。A.贴现法
适用于原始投资相同,而项目寿命期不同的互斥方案比较决策的评价方法是()。A.现
企业要充分利用各种筹资渠道,选择经济、可行的资金来源所涉及的筹资管理原则是()
优化资本结构的方法有:高低点法、公司价值分析法和平均资本成本法。
半变动资金可采用一定的方法划分为不变资金、变动资金和半变动资金。
下列关于支付方法的说法中,正确的有()。A.在收款法下,借款人收到款项时就要支
在利益冲突协调中,所有者与经营者的利益冲突协调方法主要有:解聘、接收和激励。
下列各项中,属于协调所有者和经营者矛盾的方法是()。A.限制性借债 B.停止
定期预算编制方法的缺点是()A.缺乏长远打算,导致短期行为出现 B.工作量大
能够使预算期间保持为一个固定长度的预算方法为()。A.弹性预算 B.固定预算
随机试题
MuslimSudanisoneoftheIslamized【B1】______regions.InEastAfricamusi
Mistakesarethethingsthatnobodywants,butwestillmakemistakesatany
ThismonthSingaporepassedabillthatwouldgivelegalteethtothemoral
由于原材料发生变化,或者临时他人顶班作业造成的直方图为()A.折齿型 B.左
Mostoperatingsystemshaveastandard
单只私募证券投资基金管理规模金额达到( )万元以上的,应当持续在每月结束之日起
A.高山病 B.糖尿病酮症酸中毒 C.中毒型细菌性痢疾 D.原发性癫痫
对招标项目的投标人在研究招标文件和现场考察后提出的质疑,招标人的正确处理方式有(
美国实用主义教育家( )提出了“学校即社会”的主张,试图调和个人本位和社会本位
以下用药错误的事例中,属于"管理缺失"的是A.同种药物不同规格 B.药品包装外
最新回复
(
0
)