“学习树”是哪种数据结构？

Question

我想表达的是：要了解幂，我需要知道乘法，而要了解乘法，我需要知道加法。所以要了解A，我需要知道B，或者A依赖于B。我只能想到几个规则：如果A依赖于B，B就不能依赖于A。如果A依赖于B，B又依赖于C，那么C就不能依赖于A。

这种数据结构有名称吗？我认为它不是分层树。还有，我是否漏掉了其他规则？如果我想以这种方式实现人类知识的映射，那么如果我问我的数据库我需要了解什么才能学习量子物理学，它将给我一个有序的列表，列出量子物理学所依赖的主题。当然，这个列表可能有一些并行的子列表，也就是说，A可能依赖于B和C，而B不依赖于C或C不依赖于B。在这种情况下，B将与C并行，因此它们可以在同一高度下显示。

我相信还有许多其他情况使用了相同类型的结构。

编辑 那么一个偏序集怎么样？抱歉，我并不是要挑剔，但在我看来，它将同样的事情形式化，而没有任何对图形的不必要引用。

- Juan

---

也被称为“技术树”。 - David Cary

Answer 1

Such dependency constraints are usually represented by a 有向无环图, or DAG for short.

A DAG is a 图 which is

• 有向的

  ...since each edge represents a dependency, and a dependency has a direction. If "A depends on B" you have A → B.

• 无环的

  ...since (as you point out in your post) it is undesirable to have cyclic dependencies.

- aioobe

---

这是否也可以是一个部分有序集？ - Juan

是的，DAG 定义了一个（严格的）偏序集合（或者换句话说，DAG 是表示（严格的）偏序集合的一种方式）。 - aioobe

Answer 2

这只是一个有向无环图（Directed Acyclic Graph）。

- Konrad Rudolph

Answer 3

是的：这个结构是一个有向无环图（DAG）。

- Matthew Slattery

Answer 4

是的，DAG（有向无环图）是最常用的！请参见这里：https://en.wikipedia.org/wiki/Directed_acyclic_graph。

- Joejoe

Answer 5

这通常是使用图形实现的。

- Emil Vikström