<p>正如其他人提到的,问题是找到<a href="https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/" rel="noreferrer">longest path in a directed acyclic graph</a>。在</p>
<p>对于Python中与图形相关的任何东西,<a href="https://networkx.github.io/" rel="noreferrer">networkx</a>是您的朋友。在</p>
<p>您只需初始化图形,添加节点,添加边并启动<a href="https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.dag_longest_path.html" rel="noreferrer">^{<cd1>}</a>:</p>
<pre><code>import networkx as nx
import matplotlib.pyplot as plt
words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat',
'hedgehog', 'mouse']
G = nx.DiGraph()
G.add_nodes_from(words)
for word1 in words:
for word2 in words:
if word1 != word2 and word1[-1] == word2[0]:
G.add_edge(word1, word2)
nx.draw_networkx(G)
plt.show()
print(nx.algorithms.dag.dag_longest_path(G))
</code></pre>
<p><a href="https://i.stack.imgur.com/KEmFw.png" rel="noreferrer"><img src="https://i.stack.imgur.com/KEmFw.png" alt="enter image description here"/></a></p>
<p>It输出:</p>
^{pr2}$
<p>注意:此算法仅在图中没有循环(循环)时有效。这意味着它将以<code>['ab', 'ba']</code>失败,因为有一条无限长的路径:<code>['ab', 'ba', 'ab', 'ba', 'ab', 'ba', ...]</code></p>