首页
登录
公务员类
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
免费题库
2022-08-02
112
问题
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。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.固定预算
随机试题
Theunderlinedwords"thesedevelopments"inparagraph2mostprobablyreferto
[originaltext]GeneralizingabouteducationintheUnitedStatesinvolvesso
[originaltext]W:Jack,wouldyouminddrivingmetothestation?M:Sure,why
Howmenfirstlearnedtoinventwordsisunknown;inotherwords,theorigin
路面基层施工中,用于稳定土质或路基填筑土方所必需的机械是()。A.平板拖车组
下列()颜色的波长为最短。A.紫色 B.黄色 C.红色 D.绿色
符合慢性病性贫血的实验室检查的是A.血红蛋白多数小于60g/L B.多数为小细
截至2015年底,中国创业投资各类机构数已达1775家,同比增长14.4%。其中
()按交易所上市的同一股票的市价估值。A:首次发行未上市的股票B:送股、转增股
逆行性牙髓炎不同于其他牙髓炎的临床表现特点是A:冷测缓解疼痛 B:有阵发性自发
最新回复
(
0
)