试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。给出算法的基本设计思想以及结点和邻接表的定义。

admin2017-04-28 37

问题试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
给出算法的基本设计思想以及结点和邻接表的定义。

选项

答案基本设计思想：若存在这样的顶点，该顶点到其他任一结点都有一条有向路，又因为该有向图是无环路的，那么该顶点到这些结点之间的路构成一棵树，此树上的结点数应该等于该图的结点数。若不等于（小于），则不存在这样的结点。因此，从任意结点开始，遍历此图（深度优先或者是广度优先均可），若visited的结点数等于图的结点数，则存在，否则不存在。结点和邻接表定义如下：struct node{ int adjvex； node *next；}；//结点的定义struct g{ vertexttype data； node *firstarc；Jtypedef g ADJLIST；//邻接表的定义

解析

转载请注明原文地址:https://kaotiyun.com/show/JJRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。给出算法的基本设计思想以及结点和邻接表的定义。

计算机408

学硕统考专业

简述两税法产生的背景、内容及其评价。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

美国主张建立国际联盟的主要目的是()。

“二战”后，联合国的成立反映了世界人民和平的愿望，下列叙述正确的是()。

最早以立法形式巩固大化改新成果的法令是()。

明朝中叶，美洲高产的农作物()的传入，对改变当时人们的食品结构产生了重大影响。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

盐可促进或抑制酵母菌的繁殖，达到调节主坯发酵速度的作用。()

踝关节

A、蓄积B、第一相反应C、药物相互作用D、生物利用度E、酶诱导作用某些药物可使体内药酶活性、数量升高

肝脏手术后最严重的并发症是下列哪项()

资本资产定价模型(CAPM)中的贝塔系数测度的是()。

会计的监督职能是会计人员在进行会计核算的同时，对特定会计主体经济活动的合法性、合理性的审查。()

在我国，行政主体可以分为()。

Atthebeginningofthetwentiethcentury,NorthAmericansocietyheld,asanideal,theNuclearFamily.Thispresumablyperfect

试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 给出算法的基本设计思想以及结点和邻接表的定义。

计算机408

学硕统考专业

简述两税法产生的背景、内容及其评价。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

美国主张建立国际联盟的主要目的是()。

“二战”后，联合国的成立反映了世界人民和平的愿望，下列叙述正确的是()。

最早以立法形式巩固大化改新成果的法令是()。

明朝中叶，美洲高产的农作物()的传入，对改变当时人们的食品结构产生了重大影响。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

盐可促进或抑制酵母菌的繁殖，达到调节主坯发酵速度的作用。()

踝关节

A、蓄积B、第一相反应C、药物相互作用D、生物利用度E、酶诱导作用某些药物可使体内药酶活性、数量升高

肝脏手术后最严重的并发症是下列哪项()

资本资产定价模型(CAPM)中的贝塔系数测度的是()。

会计的监督职能是会计人员在进行会计核算的同时，对特定会计主体经济活动的合法性、合理性的审查。()

在我国，行政主体可以分为()。

Atthebeginningofthetwentiethcentury,NorthAmericansocietyheld,asanideal,theNuclearFamily.Thispresumablyperfect

试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。给出算法的基本设计思想以及结点和邻接表的定义。