我正试图设计一种在O(n+m(时间内运行的算法，以确定给定有向无环图中是否存在哈密顿路径。
这里有一个解决这个问题的算法：
对DAG执行拓扑排序，然后检查排序中的连续顶点是否在图表如果是这样的话，拓扑排序给出了一个哈密顿路径。另一方面，如果存在一个哈密顿量路径，则该路径给出了DAG的拓扑排序。
现在我不知道如何证明它的正确性和找出它的空间复杂性。如有任何帮助，我们将不胜感激。
实际上，您自己几乎已经证明了这一点。你的证明中缺少的部分是表明，如果DAG有一个哈密顿路径，那么拓扑排序算法必须找到它，因为没有其他方法可以将节点按拓扑排序：
假设存在一条哈密顿路径。设
u和v是任意两个节点，并在不失一般性的情况下假设在哈密顿路径中u出现在v之前。然后在u和v之间的哈密顿路径中的节点形成了从u到v的路径，所以在任何拓扑排序顺序中，u都必须出现在v之前。因此，拓扑排序顺序中的所有节点对都具有与哈密顿路径中相同的相对排序。因此，如果节点是拓扑排序的，那么它们与哈密顿路径的顺序相同。
因此，如果存在哈密顿路径，运行任何拓扑排序算法都会找到它；如果没有哈密顿路径，那么拓扑排序当然找不到。
关于空间复杂性，这将与拓扑排序算法的空间复杂性相同，因为检查结果是否为哈密顿路径的第二阶段需要O(1(额外空间。标准拓扑排序算法的空间复杂度是O(n(，其中n是顶点的数量。