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

Question

我目前正在开发一个本体，一个网络层次结构的分类的一切(想想人，地点，事物)。最终的产品应该允许我从科技->计算机->笔记本电脑>USB端口导航，但也可以从电影->少数族裔报告->计算机->等等。我需要一个有效的数据结构来分组这些。我需要一个树样的图形，但一个特殊的树，允许子节点有多个父节点。在思考这个问题时，我意识到维基百科是一个不完美的模式。事实上，他们有一个启动这里的层次结构，这正是我所需要的。我看到他们使用有向图，但我想知道这个有向图、一个有向无圈图和一个多树之间有什么区别/缺点。我试过研究它，但我不太明白其中的区别。任何帮助都将不胜感激。谢谢!

Answer 1

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

• 有向图是由边缘连接的一组节点，边缘具有与其相关联的方向。
• 有向无圈图是一个没有有向循环的有向图。
• 多树 (也称为有向树)是一个有向图，它在任意两个顶点之间都有一条无向路径。换句话说，多树是一个有向图，它的底层无向图是树，或者等价地说是一个已连接有向无圈图，对于它也没有无向圈。

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