3

DAG 可以有多个父级和/或多个根吗?

4

2 回答 2

1

DAG 中没有任何内容可以防止节点拥有多个父节点。同样,没有什么能阻止 DAG 拥有多个根。因此,是的,您可以在 DAG 中拥有这两个功能。

于 2017-11-30T20:00:21.587 回答
1

DAG是一个沿一个方向流动的图,其中没有元素可以是其自身的子元素。对于图形的单个节点,您仍然可以有多个子节点和多个父节点

在此处输入图像描述

图由顶点和边的集合形成,其中顶点是通过边成对连接的无结构对象。在有向图的情况下,每条边都有一个方向,从一个顶点到另一个顶点。有向图中的一条路径可以用一系列边来描述,边的序列中每条边的结束顶点与序列中下一条边的起始顶点相同;如果一条路径的第一条边的起始顶点等于其最后一条边的结束顶点,则一条路径形成一个循环。有向无环图是没有环的有向图

资料来源:维基百科

至少,有向无环图必须具有:

  • 节点:存储数据的地方。
  • Directed Edges:指向一个方向的箭头(使这个数据结构不同的东西)
  • 一些没有父母的伟大祖先节点。(有趣的事实:大多数祖先树实际上是有向无环图而不是真正的树,因为表亲有时会结婚。)
  • 叶:没有子节点的节点
于 2017-11-09T17:14:29.283 回答