Python - 寻找最长路径

Question

该函数以字典为输入，并需要找到字典中最长路径的长度。基本上，如果在字典中，key2与value1匹配，key3与value2匹配，以此类推，这就是一条路径。例如：

{'a':'b', 'b':'c', 'c':'d'}

在上面的情况下，长度应该是三。我该如何实现这一点？或者更具体地说，我该如何比较键和值？（可以是任何东西，字符串、数字等，不仅仅是数字）

非常感谢您的帮助！

- aRandomStudent

---

为什么需要“将键与值进行比较”？ - Nir Alfasi

我不知道如何进行其他检查... 我是编程新手。 - aRandomStudent

你是否可能有一个循环，例如 {'a':'b', 'b':'c', 'c':'d', 'd' : 'a'}？ - DYZ

是的！函数应该终止并发出警告。否则长度将是无限的。 - aRandomStudent

Answer 1

我会把字典视为有向无环图(DAG)中的边列表，并使用networkx模块来查找图中最长的路径:

import networkx as nx

data = {'a':'b', 'b':'c', 'c':'d'}

G = nx.DiGraph()
G.add_edges_from(data.items())
try:
  path = nx.dag_longest_path(G)
  print(path)
  # ['a', 'b', 'c', 'd']

  print(len(path) - 1)
  # 3
except nx.exception.NetworkXUnfeasible: # There's a loop!
  print("The graph has a cycle")

- DYZ

---

必须存在。但为什么呢？您将不得不重新实现 networkx 的功能。 - DYZ

如果你仍然决定去做，那么前方将是一条漫长而曲折的道路，以下是开始的地方：https://dev59.com/3nzaa4cB1Zd3GeqPS633 - DYZ

@Yvonne 我会选择这个解决方案。寻找最长路径是NP完全问题（类似于“旅行商人”问题），你更愿意选择一个精心设计的解决方案，而不是在stackoverflow答案中随便想出来的解决方案。否则你会遇到非常慢的运行时间。 - hansaplast

注意：github上的networkx版本现在也支持加权边 :) - mathandy

这是我测试过的最有效的方法，我的数据字典中有1000多条记录，速度真的很快，谢谢！ - Xiaohong Yuan

Answer 2

如果你坚持不导入任何内容，你可以这样做：

def find_longest_path(data):
    longest = 0
    for key in data.iterkeys():
        seen = set()
        length = -1
        while key:
            if key in seen:
                length = -1
                raise RuntimeError('Graph has loop')
            seen.add(key)
            key = data.get(key, False)
            length += 1
        if length > longest:
            longest = length

    return longest

- Batman

---

raise RuntimeError('Graph has loop') 会使 length=-1 和 break 变得不必要。 - DYZ

你说得对。我在重新阅读问题后添加了 RuntimeError。 - Batman