数据结构：类似维基百科的树

Question

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

Answer 1

我认为维基百科的文章给出了很好的概述：

• 有向图是由边连接的一组节点，边具有与其关联的方向。
• 有向无环图（DAG）是没有有向环的有向图。
• 多叉树（也称为有向树）是一种有向图，任意两个顶点之间只有一条无向路径。换句话说，多树是一个有向图，其底层无向图是一棵树，或者等效地，一个连接的有向无环图，其中也没有无向循环。

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