首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
76
问题
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析：无论是采用深度优先遍历还是广度优先遍历，可知每个结点均访问了一次，因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。
在1945年提议战后有必要建立一个普遍性的国际组织(即后来的联合国)，以维持国际和平与安全的国家不包括()。
古文经学家()为了反对今文经派根据隶定的古书穿凿附会而曲解经文，于是编成一部《说文解字》，共收小篆及其他古文字9353个，逐字注释其形体音义。
原始人群是人类最早的社会组织形式，这种社会组织组成的纽带是()。
下列关于1929～1933年经济危机的描述，错误的有()。
阅读下列材料，回答问题：材料一：列宁说：“我们在夺取政权时便知道，不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
阅读史料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为
阅读史料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为
晚清时期清帝年号的正确排序是
某机的主要部件如下图所示。(1)请补充各部件间的主要连接线，并注明数据流动方向。(2)拟出指令SUB(R1)，一(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作，源操作数地址和目的操作数地址分别在
随机试题
()是绩效管理过程的起点。
黄河公司现已拥有资金总额1000万元，其中股本200万元(每股面值1元、发行价格3．5元)、长期债券300万元(年利率为8％)。黄河公司为生产A产品，急需购置一台价值为250万元的W型设备，该设备购入后即可投入生产使用。预计使用年限为4年，预计净残值为1
为向A公司支付购买机器设备的货款，B公司向自己开户的C银行申请开具银行承兑汇票。C银行审核同意后，B公司依约存入C银行300万元保证金，并签发了以自己为出票人、A公司为收款人、C银行为承兑人、金额为1000万元、见票后3个月付款的银行承兑汇票，C银行在该汇
对于培养学生智力技能具有现实意义的途径是()
治安行政管理工作的内容包括户籍管理工作、公共秩序管理工作、特种行业管理工作、民用危险物品管理工作、交通安全管理工作、消防工作、边防工作、外国人管理和中国公民出入境管理工作等内容。( )
原告系从事货物运输业车主。2008年4月9日，原告受被告委托运输货物，当天下午3时许，原告驾车将货物运送至被告公司内，刚下车不久，即被被告用铁链栓养在公司内的犬咬伤左膝，当即被告派员将原告送往医院治疗。事后，就赔偿一事双方协商未成，原告诉诸法院，要求被告赔
大学生的就业牵涉自身和千家万户的利益，牵涉国家和社会的利益。对大学生来说，应当树立正确的择业观，体现为()
信息系统运行管理工具不包括(46)。
Ithasalwaysbeenaproblemtodecidewhether"popularmusic"ismusicwhichrepresentsthepeopleorissimplymusicthatthe
A.interactionB.experiencedC.reflectD.responseE.undertakenF.affectG.althoughH.frustrationI.subjectJ.sufficient
最新回复
(
0
)
