5

I am currently in the process of developing an ontology, a web hierarchy of categories of everything (think persons, places, things). The finished product should be something that allows me to navigate from Technology->Computers->Laptops->USB Ports, but also from Movies->Minority Report->Computers->etc. I need an efficient data structure to group these. I need a tree-like graph, but a special tree that allows child nodes to have multiple parent nodes. In thinking over this, I have realized that Wikipedia is an imperfect model for this. In fact, they have a hierarchy starting here that is essentially exactly what I need. I see that they used a directed graph, but I am wondering what the differences/drawbacks between this directed graph, a directed acyclic graph, and a polytree are. I have tried researching it, but I don't quite understand the differences. Any help would be greatly appreciated. Thank you!

4

1 回答 1

2

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

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

所以我认为你搜索一个连通的有向无环图。尽管 Wikipedia 类别系统允许循环，但它们是不需要的。

于 2012-06-07T16:10:01.090 回答