时间戳

首页 > 解决方案 > 如何识别python字典中的根节点？

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

问题描述

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

下面是一个示例字典：

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

我会将这个过程分成不同的框架。取决于上述字典的预期结果如下：

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

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

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

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

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

我一直在阅读有关Dask和luigui的信息，但不确定它们是否是最终解决方案，或者我可以通过一些简单的方式来实现。

标签： pythondata-structuresgraph

解决方案

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

  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]

推荐阅读