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

admin2017-04-28 83

问题试设计一个算法，判断一个有向无环图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

学硕统考专业

《关于建国以来党的若干历史问题的决议》

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

英国在准备撤出印度时采取的策略是()

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

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

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

加尔文教传播到法国后，其信仰者被称为()。

政协全国委员会常委会会议一般()

A．文火B．中火C．武火D．先文火后武火E．先武火后文火苍耳子炒黄多用

口腔颌面损伤后患者鼻或耳流出带血的水样液体可诊断为

新生儿硬肿症重症的肛温

张某因抢劫罪被某区人民法院判处有期徒刑8年。宣判后张某不服，以自己有法定从轻情节、原审法院量刑过重为由提起上诉。市中级人民法院对此案进行了二审。请问：中级人民法院审理该案的方式有哪些?

考虑到反射太阳辐射和避免产生眩光，遮阳构件的颜色应为()。

如果国债承销价格定价过低，投资者就会倾向于二级市场上购买已流通的国债，而不是直接购买新发行的国债，从而阻碍国债分销工作顺利进行。()

根据增值税法律制度的规定，纳税人销售货物出现的下列情况中，不得自行开具增值税专用发票的有()。

2016年6月1日，第十一届光华工程科技奖颁奖大会在京举行，34位工程科技专家获得奖励。其中，()荣获光华工程科技奖“成就奖”。

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

计算机408

学硕统考专业

《关于建国以来党的若干历史问题的决议》

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

英国在准备撤出印度时采取的策略是()

战时共产主义政策中对后来的工农联盟最能构成威胁的是()。

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

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

加尔文教传播到法国后，其信仰者被称为()。

政协全国委员会常委会会议一般()

A．文火B．中火C．武火D．先文火后武火E．先武火后文火苍耳子炒黄多用

口腔颌面损伤后患者鼻或耳流出带血的水样液体可诊断为

新生儿硬肿症重症的肛温

张某因抢劫罪被某区人民法院判处有期徒刑8年。宣判后张某不服，以自己有法定从轻情节、原审法院量刑过重为由提起上诉。市中级人民法院对此案进行了二审。请问：中级人民法院审理该案的方式有哪些?

考虑到反射太阳辐射和避免产生眩光，遮阳构件的颜色应为()。

如果国债承销价格定价过低，投资者就会倾向于二级市场上购买已流通的国债，而不是直接购买新发行的国债，从而阻碍国债分销工作顺利进行。()

根据增值税法律制度的规定，纳税人销售货物出现的下列情况中，不得自行开具增值税专用发票的有()。

2016年6月1日，第十一届光华工程科技奖颁奖大会在京举行，34位工程科技专家获得奖励。其中，()荣获光华工程科技奖“成就奖”。

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