algorithm - 排序一些节点的算法

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，并且您正在寻找拓扑排序。

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

编辑：如果图表是森林（树的不相交联合） - 那么来自源的简单DFS就可以了。只需构建图（就是O(nlogn)排序，如果还没有排序，或者O(n)使用基数排序），找到源列表，对每个源做DFS，每次访问一个节点，将其存储在一个输出中大批。在有未发现的顶点时进行迭代。