首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
58
问题
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
苏台德问题
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
以下选项不属于希腊城邦的形成方式和途径的是()。
中国共产党制定的抗日民族统一战线策略总方针的中心环节是()。
开皇五年,文帝规定每年正月五日县令出查,令百姓五党三党为一团,根据标准定户等上下,从轻制定税额,并将各户应纳税额写成定簿,是为()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
近代思想家如何传播西方思想革新中国政治的?
欧洲历史上第一部系统完备的法典是()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
随机试题
“酒逢知己饮,诗向会人吟”,表现的人际吸引的条件是()
半刚性基层沥青面层弯沉测试中,当()时应进行温度修正。
招标代理机构可以不具备的条件是()。
某机电安装工程项目,业主通过公开招标方式选择了某机电安装企业,双方签订了机电安装工程施工总承包合同,施工总承包企业又选择了一家劳务分包企业,将某分部工程的劳务作业分包给该劳务分包企业。在施工过程中发生如下事件:事件1:由于业主供应的工程材料延误,使劳务分
某企业于9月1日持一张面值为100000元,利率为10%,出票日为5月1日,到期日为11月1日的商业汇承兑汇票到开户银行贴现,贴现率为9%。该企业所得贴现额为()元。
下列说法或做法中不符合现行《中小学教师职业道德规范》中的“教书育人”规定和要求的是()。
领导安排你组织一个单位的春节联欢晚会.你怎么把这个活动落到实处?
国民议会运动
波尔卡是()民间舞蹈。
现行PC机普遍采用的ISA总线(AT总线)扩充插槽可供插卡使用的硬中断有 ( )。
最新回复
(
0
)