3 回答
您不是在寻找哈密顿循环（即开始 = 开始），而是寻找哈密顿路径，这也是一个 NP 完全问题。但是，您的图表不是通用的，因为只有 26 个字母。如果您允许超过 26 个字母的符号，那么它实际上等同于哈密顿寻路。
这是一个解决方案：您应该反过来思考：
- 图的顶点是 26 个字母。
- 对于每个以 x 开头并以 y 结尾的单词，字母 x 和 y 之间都有一条边
因此，您得到的实际上是一个多重图，因为多个单词可以以相同的字母开头和结尾。那么你正在寻找的东西被称为欧拉路径：它是一条每条边都恰好一次的路径。寻找欧拉路径是一个多项式问题（https://en.wikipedia.org/wiki/Eulerian_path）。它实际上可能是历史上第一个图形问题之一。
现在引用维基百科：
有向图有欧拉轨迹当且仅当至多一个顶点有 (out-degree) - (in-degree) = 1，至多一个顶点有 (in-degree) - (out-degree) = 1，每其他顶点具有相等的入度和出度，并且其所有具有非零度的顶点都属于底层无向图的单个连通分量。
与搜索哈密顿路径相比，这是确定是否存在路径的更好方法。
此处回答了类似的问题：Detecting when matrix multiplication is possible
您可以将其解决为欧拉路径问题，它比哈密顿路径简单得多。
不要让每个字符串成为图中的节点，而是让每个字母成为图中的节点。如果字符串从第一个字母开始并以另一个字母结束，则在两个字母之间添加有向边。现在在此图中找到一条欧拉路径将为您提供所需的解决方案。
假设您有一个大小为 26 的字母表。
让我们把你的单词想象成一个有向图，有 26 个顶点对应于所有字母 {a, b, ..., z}。
对于您拥有的每个单词，在图表中添加一条有向边——从单词的开头字母到结尾的字母。
然后你正在寻找这个图的欧拉路径 - 访问每条边的路径（通过你的每个单词）恰好一次。
有一个著名的定理：
n 个顶点上的有向图 G 有一个欧拉路径 iff。至少 n-1 个顶点的入度等于出度。
此外，还有一些算法可以在多项式时间内构建这样的游览，例如 Fleury 算法。