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

Question

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

performancedata-structurestreehierarchywikipedia

5

我目前正在开发一个本体论，这是一种万物分类的Web层次结构（比如人、地方、事物等）。最终产品应该是允许我从“技术”-〉“计算机”-〉“笔记本电脑”-〉“USB端口”进行导航，并且也允许我从“电影”-〉“少数派报告”-〉“计算机”-〉等进行导航。我需要一种高效的数据结构来对它们进行分组。我需要一个树状图，但这个特殊的树状图允许子节点有多个父节点。在思考这个问题时，我意识到维基百科并不是一个完美的模型。实际上，他们开始使用的层次结构 here 正是我需要的东西。我看到他们使用了一个有向图，但我想知道这个有向图、有向无环图和多叉树之间的区别和缺点。我已经尝试过研究，但我还没有完全理解其中的区别。任何帮助都将不胜感激。谢谢！

- Ruben Martinez Jr.

1

顺便说一句：维基百科的分类允许循环，尽管社区不希望出现这种情况。德语系统是一个更好的多树示例，以!Hauptkategorie为根。 - Bergi

1

你是不是指的是本体论（ontology）？否则这听起来就像一个普通的有向图。 - Konrad Rudolph

是的，我确实指的是本体论。感谢您使用了适当的行话 :) - Ruben Martinez Jr.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bergi · Accepted Answer

我认为维基百科上的文章提供了很好的概述：

有向图是由边连接的节点集合，这些边具有与之相关联的方向。
有向无环图（DAG）是没有有向环的有向图。
有向树（也称为有向树）是一个有向图，其中任意两个顶点之间恰好存在一条未定向路径。换句话说，有向树是一个其底层未定向图是树的有向图，或者等价地说，是一个连通的有向无环图，其中也没有未定向环。

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