performance - 数据结构 : Wikipedia-like Tree

Question

我目前正在开发一个本体，一个所有事物类别的网络层次结构(想想人、地方、事物)。成品应该能让我从技术->计算机->笔记本电脑->USB端口导航，但也可以从电影->少数派报告->计算机->等导航。
我需要一个有效的数据结构来对这些进行分组。我需要一个树状图，但需要一个特殊的树，它允许子节点有多个父节点。
在考虑这一点时，我意识到维基百科是一个不完美的模型。事实上，他们有一个从 here 开始的层次结构。这基本上正是我所需要的。我看到他们使用了有向图，但我想知道这个有向图、有向无环图和多叉树之间的区别/缺点是什么。我试过研究它，但我不太明白它们的区别。任何帮助将不胜感激。谢谢!

Answer 1

我认为维基百科上的文章给出了一个很好的概述:

一个 directed graph是一组由边连接的节点，这些边有一个与它们相关联的方向。

一个 directed acyclic graph (DAG) 是一个没有 directed cycles 的有向图.

一个 polytree (也称为有向树)是一种有向图，在任意两个顶点之间只有一条无向路径。换句话说，polytree 是一个有向图，其底层无向图是 tree ，或等效地，一个 connected也没有无向环的有向无环图。

所以我认为你在寻找一个连通的有向无环图。尽管维基百科分类系统允许循环，但它们是不需要的。