首页
登录
公务员类
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
免费题库
2022-08-02
30
问题
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。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://www.tihaiku.com/gongwuyuan/2555166.html
本试题收录于:
计算机 电网题库国家电网招聘分类
计算机 电网
国家电网招聘
相关试题推荐
在短期借款的利息计算和偿还方法中,企业实际利率高于报价利率的有()。A.贴现法
适用于原始投资相同,而项目寿命期不同的互斥方案比较决策的评价方法是()。A.现
企业要充分利用各种筹资渠道,选择经济、可行的资金来源所涉及的筹资管理原则是()
优化资本结构的方法有:高低点法、公司价值分析法和平均资本成本法。
半变动资金可采用一定的方法划分为不变资金、变动资金和半变动资金。
下列关于支付方法的说法中,正确的有()。A.在收款法下,借款人收到款项时就要支
在利益冲突协调中,所有者与经营者的利益冲突协调方法主要有:解聘、接收和激励。
下列各项中,属于协调所有者和经营者矛盾的方法是()。A.限制性借债 B.停止
定期预算编制方法的缺点是()A.缺乏长远打算,导致短期行为出现 B.工作量大
能够使预算期间保持为一个固定长度的预算方法为()。A.弹性预算 B.固定预算
随机试题
Eachartistknowsinhisheartthatheissayingsomethingtothepublic.He
高速圆锥齿轮传动,当润滑不良时,最可能发生的失效形式是()。A.齿面胶合
巩膜三大薄弱处位于A.角巩膜缘、赤道部、巩膜筛板 B.角巩膜缘、肌肉附着点、赤
回答隧道消防设施检验评定方面的提问。(2)隧道消防设施检验评定实测项目中关于安装
25岁,女性,婚后2年同居,性生活正常,未孕来诊。14岁初潮,月经稀发3~6月1
(2018年真题)在私募股权基金有限合伙制下,下列关于普通合伙人表述中,正确的是
根据《关于证券从业人员登记管理有关事项的通知》,从业人员等级类别设为( )。
小儿纯阳之体的含义是A.盛阳 B.纯阳无阴 C.阳常有余 D.阴虚阳盛
完善的社会保障体系是社会和谐稳定的安全网。“十二五”期间,北京市人力社保部门将加
“意识是客观存在的主观映象”的命题是指( ) A.意识是主体和客体连结和转化
最新回复
(
0
)