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 回答