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

admin2017-04-28 78

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

中世纪西欧城市形成的过程及其对西欧社会产生的影响。

1962年初，中共召开了中央工作会议，即“七千人大会”，其议题主要是()。

利玛窦与徐光启合作翻译的()，介绍了曾经流行于欧洲的欧几里得平面几何的系统理论，大大地丰富了中国古代几何学的内容。

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

中国共产党制定的抗日民族统一战线策略总方针的中心环节是()。

1962年1、2月间，中共中央召开的统一思想、总结经验教训、明确工作方向的会议是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

在网络中计算机接收的信号是()。

A．消毒B．灭菌C．防腐D．无菌E．无菌操作注射前用碘伏处理属于

A、低盐，优质低蛋白饮食B、低盐、高糖饮食C、低盐、高蛋白饮食D、低盐、高钙饮食E、饮食清淡、易消化、富有营养对慢性肾盂肾炎病人应采用（）

畸胎瘤为

新修订的《传染病防治法》增加的乙类传染病是哪些

施工过程中降低成本的()，包括进行技术经济分析，确定最佳的施工方案等。

由于业主原因导致承包商自有施工机械停工，承包商应按()索赔计算窝工费。

公共联合融资常见的手段包括()。

七艺

权力制约是指国家机关的权力必须受到法律的规制和约束，也就是要把权力关进制度的笼子里。约束权力的最大的笼子是()

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

计算机408

学硕统考专业

中世纪西欧城市形成的过程及其对西欧社会产生的影响。

1962年初，中共召开了中央工作会议，即“七千人大会”，其议题主要是()。

利玛窦与徐光启合作翻译的()，介绍了曾经流行于欧洲的欧几里得平面几何的系统理论，大大地丰富了中国古代几何学的内容。

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

中国共产党制定的抗日民族统一战线策略总方针的中心环节是()。

1962年1、2月间，中共中央召开的统一思想、总结经验教训、明确工作方向的会议是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

在网络中计算机接收的信号是()。

A．消毒B．灭菌C．防腐D．无菌E．无菌操作注射前用碘伏处理属于

A、低盐，优质低蛋白饮食B、低盐、高糖饮食C、低盐、高蛋白饮食D、低盐、高钙饮食E、饮食清淡、易消化、富有营养对慢性肾盂肾炎病人应采用（）

畸胎瘤为

新修订的《传染病防治法》增加的乙类传染病是哪些

施工过程中降低成本的()，包括进行技术经济分析，确定最佳的施工方案等。

由于业主原因导致承包商自有施工机械停工，承包商应按()索赔计算窝工费。

公共联合融资常见的手段包括()。

七艺

权力制约是指国家机关的权力必须受到法律的规制和约束，也就是要把权力关进制度的笼子里。约束权力的最大的笼子是()

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