给定一个非循环有向图，返回“同一级别”的节点集合的集合？

Question

首先，我不确定这样的算法叫什么，这是主要问题 - 所以问题的第一部分是这个算法叫什么？

基本上我有一个DiGraph()插入节点[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]和边缘的([1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10])

由此我想知道是否有可能获得如下集合：[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]

编辑：如果有帮助的话，让我添加一些限制。- 没有循环，这是有保证的 - 图表没有一个起点

我想做的是收集同一级别的节点，以便它们的处理可以并行化，但在外部集合中，处理是串行的。

编辑2：很明显，我没有充分考虑这一点，因此描述“级别”的最简单方法是最深的前驱，即具有相同前驱深度的所有节点。因此，上面列表中的第一个条目都是最深前驱为 0 的节点，第二个条目为 1，第三个条目为 2，依此类推。在每个列表中，同级的顺序无关紧要，因为它们将被并行处理。

Answer 1

您的问题表明您希望该图的输出为[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]。IIUC，模式如下：

• [1, 2, 4, 6]是没有边的节点。

• [3]是没有边的节点，假设所有先前的节点都被删除。

• [4]是没有边的节点，假设所有先前的节点都被删除。

• 等等（直到所有节点都被擦除）

假设我们从

g = networkx.DiGraph()
g.add_edges_from([[1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10]])

然后我们可以将其编码为

def find_levels(g):
    levels = []
    while g.nodes():
        no_in_nodes = [n for (n, d) in g.in_degree(g.nodes()).items() if d == 0]
        levels.append(no_in_nodes)
        for n in no_in_nodes:
            g.remove_node(n)
    return levels

如果我们运行这个，我们会得到结果：

>>> find_levels(g)
[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]

这里的复杂度是θ(|V| ² + |E|)。可以使用斐波那契堆构建稍微复杂的版本。基本上，所有顶点都需要放入堆中，每个级别由度数为 0 的顶点组成。每次弹出一个顶点，并且删除其他顶点的边时，我们可以将其转换为堆减少键操作（减少剩余顶点的入度）。这会将运行时间减少到θ(|V| log(|V|) + |E|)。