首先，我不确定这种算法称为什么，这是主要问题——因此第一个问题是这个算法叫什么？
基本上，我有一个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个祖先，依此类推。在每个列表中，兄弟姐妹的顺序是无关紧要的，因为它们将被并行处理。
[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]。如果我理解正确，模式如下：
[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|2 + |E|)。可以使用Fibonnacci Heap构建一个稍微复杂一些的版本。基本上，所有顶点都需要放入堆中，每个级别包含入度为0的顶点。每次弹出一个顶点并删除到其他顶点的边缘时，我们可以将其转换为堆减少关键操作（剩余顶点的入度减少）。这将减少运行时间至Θ(|V| log(|V|) + |E|)。
1时，3/5/7的“级别”发生了变化。 - Nim如Ami所说，拓扑排序可以实现此目的。以下是一个Boost Graph Library实现，没有上下文，但可以提取伪代码。 toporder对象只提供了拓扑排序的迭代器。如果需要，我可以提取一般算法。
template<typename F>
void
scheduler<F>::set_run_levels()
{
run_levels = std::vector<int>(tasks.size(), 0);
Vertexcont toporder;
try
{
topological_sort(g, std::front_inserter(toporder));
}
catch(std::exception &e)
{
std::cerr << e.what() << "\n";
std::cerr << "You most likely have a cycle...\n";
exit(1);
}
vContIt i = toporder.begin();
for(;
i != toporder.end();
++i)
{
if (in_degree(*i,g) > 0)
{
inIt j, j_end;
int maxdist = 0;
for(boost::tie(j,j_end) = in_edges(*i,g);
j != j_end;
++j)
{
maxdist = (std::max)(run_levels[source(*j,g)], maxdist);
run_levels[*i] = maxdist+1;
}
}
}
}
我认为我曾经将此应用于同样的问题，然后意识到这是不必要的。只需设置任务的触发器，所有任务都通过条件变量和promise向其依赖项发出完成信号。因此，我只需要知道每个任务的依赖关系，找到初始任务，然后启动即可。在您的情况下，是否需要完整的run_level规范？
run_level并结合拓扑排序能够帮助我在单次遍历中处理树，这样我就不需要像你描述的那样使用倒计时门闩了，我知道一旦到达下一个运行级别，所有之前的节点都已经被评估了。 - Nim
[1,2]添加到您的图形中，您希望集合是什么？ - BrenBarn