3

我一直在寻找一段时间,似乎无法找到替代解决方案。如果可能的话,我需要以这样一种方式树遍历算法,即一个节点可以有多个父节点(在此处找到一篇很棒的文章:在数据库中存储分层数据)。有没有什么算法可以让我们从一个根节点开始,确定节点的顺序和依赖关系(目前读拓扑排序)?

4

4 回答 4

2

您描述的结构不是树,而是有向图。由于它适用于分层绘图,您可能会倾向于将其视为一棵树(它本身是一个无环连通图)。

图的典型遍历算法是深度优先广度优先。图形实现只是不同,因为它记录了它已经访问过的节点,以避免多次访问某些节点。但是,如果您的数据结构保证它是非循环的,您可以通过简单地将“父母”视为“孩子”来在图表上使用树算法。

我做了一个简单的草图来说明我的意思(尝试 Google Docs 的新绘图功能的绝佳机会): 替代文字

如您所见,可以将任何具有无环有向形式的图视为树并在其上应用树算法。一旦你不能保证这个属性,你就必须使用专门的图算法。

于 2010-04-21T09:08:58.403 回答
1

树基本上是一个有向无权图,其中每个顶点有 N 或更少的边,并且不会发生循环。
如果您确定树中没有循环,则可以将父节点视为指定节点的另一个子节点,并正常执行前序遍历。
但是,如果可能发生循环,则需要图形算法。
具体来说:广度优先搜索

于 2010-04-21T09:47:36.017 回答
0

只是检查一个简单的案例:两个父母可以有不同的父母吗?如果没有,您可以将它们变成单个节点(从概念上)并再次拥有一棵树。

否则,您将不得不拆分子节点并为另一个父节点复制一个分支。(这当然会导致以后出现不一致和/或算法无效,这取决于您是否需要维护数据结构)。

如果您坚持使用树形结构,则上述选项仍然有效,根据定义,树形结构只能有一个父级。

因此,也许您需要退后一步,解释您要完成什么,以及如果节点可以有两个父节点,为什么它必须是树结构。

于 2010-04-21T10:30:11.080 回答
0

你不是在这里描述一棵树。你不能把你的图称为树。

树是无环的无向图。父/子关系不是对在边缘上绘制的方向的解释。它们是将一个顶点命名为 root的结果。

我们将一个顶点命名为“父”,因为它是根路径的下一个。与当前顶点相邻的所有其他顶点都是“孩子”。

您不能以“父母”在“上方”或“指向顶点”,而孩子在“下方”或“顶点指向他们”的方式布置任意图。一棵树之所以是一棵树,是因为它的根被采摘了。您在问题中描述的不是一棵树。并且树遍历算法不适用于遍历任意图。

有几种图遍历算法,例如广度优先搜索深度优先搜索(有关更多信息,请查看这些页面中的附注)。使用它们而不是试图将您的全功能图表与您对树的知识联系起来。

于 2010-04-21T10:30:21.610 回答