首页
登录
公务员类
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。A.求
免费题库
2022-08-02
129
问题
判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。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.固定预算
随机试题
Somedaytherewillbearobotthattakesthedrudgery(苦工,单调沉闷的工作)outofh
无论怎样划分,交通运输业都被列为()的范畴,在这一点上,经济学家和社会有
依据计量法的规定、法定计量单位是由()承认具有法定地位的计量单位。A:标准化行
下列都具有生津止渴功效的药物是()A.乌梅、生地黄、黄连 B.五味子、芦
下列除哪项外均是药材猪苓的性状鉴别特征A.呈条形、类圆形或扁块状B.表面黑色、灰
住房公积金制度的作用有()。A.增加了职工工资中的住房消费含量,实现分配体制
下列工程进度控制措施中,属于组织措施的有( )。A.采取加快工程进度的施工方法
常用冰片而不用麝香治疗的是()。A.水火烫伤 B.血滞经闭 C.咽喉肿
细菌内毒素的特征是A:只有革兰阴性细菌产生 B:少数革兰阳性细菌产生 C:细
某企业拟购买一项新技术。经调查,3年前类似技术交易转让价格为50万元。经专家鉴定
最新回复
(
0
)