algorithm - 如何修改前序树遍历算法以处理具有多个父节点的节点？

Question

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

Answer 1

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

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

我做了一个简单的草图来说明我的意思（尝试 Google Docs 的新绘图功能的绝佳机会）：

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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