我一直在寻找一段时间,似乎无法找到替代解决方案。如果可能的话,我需要以这样一种方式树遍历算法,即一个节点可以有多个父节点(在此处找到一篇很棒的文章:在数据库中存储分层数据)。有没有什么算法可以让我们从一个根节点开始,确定节点的顺序和依赖关系(目前读拓扑排序)?
4 回答
树基本上是一个有向无权图,其中每个顶点有 N 或更少的边,并且不会发生循环。
如果您确定树中没有循环,则可以将父节点视为指定节点的另一个子节点,并正常执行前序遍历。
但是,如果可能发生循环,则需要图形算法。
具体来说:广度优先搜索。
只是检查一个简单的案例:两个父母可以有不同的父母吗?如果没有,您可以将它们变成单个节点(从概念上)并再次拥有一棵树。
否则,您将不得不拆分子节点并为另一个父节点复制一个分支。(这当然会导致以后出现不一致和/或算法无效,这取决于您是否需要维护数据结构)。
如果您坚持使用树形结构,则上述选项仍然有效,根据定义,树形结构只能有一个父级。
因此,也许您需要退后一步,解释您要完成什么,以及如果节点可以有两个父节点,为什么它必须是树结构。
你不是在这里描述一棵树。你不能把你的图称为树。
树是无环的无向图。父/子关系不是对在边缘上绘制的方向的解释。它们是将一个顶点命名为 root的结果。
我们将一个顶点命名为“父”,因为它是根路径的下一个。与当前顶点相邻的所有其他顶点都是“孩子”。
您不能以“父母”在“上方”或“指向顶点”,而孩子在“下方”或“顶点指向他们”的方式布置任意图。一棵树之所以是一棵树,是因为它的根被采摘了。您在问题中描述的不是一棵树。并且树遍历算法不适用于遍历任意图。
有几种图遍历算法,例如广度优先搜索或深度优先搜索(有关更多信息,请查看这些页面中的附注)。使用它们而不是试图将您的全功能图表与您对树的知识联系起来。