对某些节点进行排序的算法

Question

我正在尝试找到一种合适的算法来解决这个问题:假设我有一些(定向图)节点。每个节点可能有或没有父节点(意味着最多有一个父节点)。假设节点的这种表示法:(id, id_parent)。一些节点将是 (id_i, NULL) 而将有节点 (id_j, id_i) 作为 id_i 的“儿子”。以特定顺序排列这些节点的数组，我想按以下顺序对它们进行排序:父-子-子之子-子-子之子等。

示例:节点 (1, NULL), (2,NULL), (3,1), (4,3), (5,2), (6,3)

排序后的数组将是:(1,NULL), (3,1), (4,3), (6,3), (2, NULL), (5,2) 。一种深入的树探索。

哪种算法适合实现此目的？谢谢

Answer 1

如果图形没有循环 - 它是 DAG , 你正在寻找 topoloical sort .

如果它有循环 - 没有这样的顺序，因为在循环中，会有一个节点，它的儿子也是它的祖先。

编辑:如果图是森林(不相交的树并集)——那么一个简单的 DFS从源头上就可以了。只需构建图形(如果尚未排序，则排序为 O(nlogn)，或者使用 radix sort 为 O(n))，找到列表来源，并从每个来源进行 DFS，每次访问节点时，将其存储在输出数组中。在有未发现的顶点时进行迭代。