python - 如何识别 python 字典中的根节点？

Question

我有一个表示图形的 python 字典。我希望识别根/独立节点，以便我可以同时处理它们，然后下一个节点将成为根/独立节点。我对如何在 python 中实现这种技术感到困惑。

下面是一个示例字典:

my_graph = {
            1:[4],
            2:[6],
            3:[9],
            4:[5,7],
            5:[8],
            6:[],
            7:[],
            8:[],
            9:[]
           }

我会把过程分成不同的帧。根据上述字典的预期结果如下:

1-开始: 根/独立节点= 1,2,3

2- 第一帧之后 根/独立节点 = 4,6,9

3- 在第 2 帧之后 根/独立节点 = 5,7

4-第3帧之后 根/独立节点 = 8

编辑 1: 我正在尝试以任何形式获取序列，例如给定字典中节点依赖图的列表、数组或任何其他类似数据结构，其中每个子节点都依赖于其父节点，因此不能在父节点之前处理。下一步，我希望获得一些并行性，即我可以一次处理所有根节点。

我一直在阅读 Dask和 luigui但不确定它们是否是最终解决方案，或者我可以用一些简单的方法来解决。

Answer 1

这称为“拓扑排序”。一个简单的算法是

1. 在节点和“传入”弧的数量之间建立映射
2. 用 0 处理节点(那些是“根”)并在您继续时更新计数器(当您处理所有邻居的节点递减计数器时)。

如果图形不是树(有环)，您可能会在完成之前停下来。在这种情况下，您将到达图形不为空但没有可用根的点。

在你的情况下

def tsort(graph): 
    counts = dict((k, 0) for k in graph) 
    for n, neighbors in graph.items(): 
        for nh in neighbors: 
            counts[nh] = counts[nh] + 1 
    while graph: 
        roots = [k for k in graph if counts[k] == 0] 
        if not roots: 
            raise RuntimeError("Cycles present, no topological sort possible") 
        print("roots", roots) 
        for r in roots: 
            print("Processing", r) 
            for nh in graph[r]: 
                counts[nh] -= 1 
            del graph[r]