首先,我不确定这种算法称为什么,这是主要问题——因此第一个问题是这个算法叫什么?
基本上,我有一个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]
添加到您的图形中,您希望集合是什么? - BrenBarn