首页
登录
公务员类
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
免费题库
2022-08-02
53
问题
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。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.固定预算
随机试题
I’mafraidthecouple’srelationshiphasbecomesobadthatitistoolateto___
AGrassrootsRemedyA)Mostofusspendourlivesseeki
Forcenturies,inthecountriesofsouthandSoutheastAsiatheelephanthas
求解微分方程:
国际收支逆差的情形是指()。A.调节性交易的收入小于调节性交易的支出 B.自主
软件系统的维护包括多个方面,增加一些在系统分析和设计阶段中没有规定的功能与性能特
电子商务发展的核心与关键问题是交易的安全性,目前安全交易中最重要的两个协议是()
妊娠43周,GP,因见红2小时,阴道流水1小时入院。询问病史以下哪项对诊断无关
下列属于股权投资基金特点的是() Ⅰ.投资期限长、流动性较差 Ⅱ.投
属于非细胞型微生物的是A.柯萨奇病毒 B.沙眼衣原体 C.钩端螺旋体 D.
最新回复
(
0
)