python - python中树中的最长路径

Question

所以，我有一个树形结构的字典。好吧，不完全是树。但是，我必须从这棵树中找到最长的路径。

这是字典:

{'1:0': [], '1:1': ['2:1', '1:0'], '1:2': ['1:3', '2:2', '1:1'], '1:3': [], '0:1': ['0:2', '1:1', '0:0'], '0:0': ['1:0'], '0:3': [], '0:2': ['0:3'], '2:3': ['2:2'], '2:2': ['3:2'], '2:1': ['2:2'], '2:0': ['2:1'], '3:2': [], '3:3': ['3:2'], '3:0': [], '3:1': ['3:2']}

实际上可能有很多根。例如，在键1:1中，它有两个子节点，其中一个是死胡同(1:0)。然后 2:1 有一个 child 2:2。此外，1:1 是 1:2

的 child

如何在 python 中编写这段代码来遍历并找到最长的路径？

Answer 1

您可以使用广度优先搜索的递归版本:

_d = {'1:0': [], '1:1': ['2:1', '1:0'], '1:2': ['1:3', '2:2', '1:1'], '1:3': [], '0:1': ['0:2', '1:1', '0:0'], '0:0': ['1:0'], '0:3': [], '0:2': ['0:3'], '2:3': ['2:2'], '2:2': ['3:2'], '2:1': ['2:2'], '2:0': ['2:1'], '3:2': [], '3:3': ['3:2'], '3:0': [], '3:1': ['3:2']}
def paths(d, _start, _current = []):
  if _current:
    yield _current
  for i in d[_start]:
     if i not in _current:
        yield from paths(d, i, _current+[i])

results = [c for i in _d for c in paths(_d, i, [i])]
_max_len = max(map(len, results))
_paths = [i for i in results if len(i) == _max_len]

输出:

[['1:2', '1:1', '2:1', '2:2', '3:2'], ['0:1', '1:1', '2:1', '2:2', '3:2']]