python - 计算由边字典定义的树图的深度

Question

我有字典，它将单个节点映射到它们连接的节点列表。我需要生成一个树形图（不是二进制），然后计算它的深度（从上到下最长的方式）。做这个的最好方式是什么？

例子：

graph = {
             1 : [],
             2 : [],
             3 : [2, 4],
             4 : [1, 5],
             5 : []
        }

答案 = 3（您需要通过最多 3 个节点才能到达底部）

标签： pythondictionarymathtreegraph-theory

Answer 1

这可以使用networkx来完成：

代码：

import networkx as nx
from networkx.algorithms.dag import dag_longest_path

graph = {
             1 : [],
             2 : [],
             3 : [2, 4],
             4 : [1, 5],
             5 : []
        }

#Create directed graph
G = nx.DiGraph(graph)

#Find longest path in tree:
path = dag_longest_path(G)

输出：

>>> path
[3, 4, 5]
>>> len(path)
3