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

Question

我有字典，可以将各个节点映射到它们所连接的节点列表。我需要生成一个树图（不是二进制的），然后计算它的深度（从上到下的最长路径）。执行此操作的最佳方法是什么？

示例：

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

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

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