枚举*all*hamiltonian路径

Question

我知道之前有人问过,但我没有在任何帖子中找到答案.有人可以建议我一个算法,列出图中的所有汉密尔顿路径？

一点背景:我正在研究一个问题,我必须列举每个汉密尔顿路径,做一些分析,然后返回结果.为此,我需要能够列举所有可能的哈密尔顿路径.

谢谢.

Answer 1

按照建议使用 BFS/DFS，但不要停留在第一个解决方案上。BFS/DFS 的主要用途（在本例中）是找到所有解决方案，您需要为其设置一个条件以在第一个解决方案处停止。