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

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

admin2017-04-28  61
问题 试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
给出算法的基本设计思想以及结点和邻接表的定义。
选项
答案基本设计思想：若存在这样的顶点，该顶点到其他任一结点都有一条有向路，又因为该有向图是无环路的，那么该顶点到这些结点之间的路构成一棵树，此树上的结点数应该等于该图的结点数。若不等于（小于），则不存在这样的结点。因此，从任意结点开始，遍历此图（深度优先或者是广度优先均可），若visited的结点数等于图的结点数，则存在，否则不存在。结点和邻接表定义如下：struct node{ int adjvex； node *next；}；//结点的定义struct g{ vertexttype data； node *firstarc；Jtypedef g ADJLIST；//邻接表的定义
解析
转载请注明原文地址:https://kaotiyun.com/show/JJRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)