Hamliton回路求解回溯pre数组也需要像visited数组一样回溯
来源：9-4 哈密尔顿回路算法的一个优化
甲骨文_0001
2021-10-17
老师，我自己理解下来写的dfs过程最后63行，我也对pre数组作了回溯, pre[v]=-1, 参考源码里这一行没有，我个人认为也需要加上去，
老师之所以没加这一行，我大概有点懂，但说不上来原因，想请老师点拨一下哈:)
写回答
1回答
-
不加没有问题，因为 dfs 本身会返回 true 或者 false，来标识是否有解，如果返回的是 false，pre 中存储的值才没有意义，但此时我们已经靠 dfs 的返回值（以及 end 的值）判断了除了 pre 的值没有意义，就不会使用了。
加上这一句的结果，是在图没有解的时候，所有的 pre 恢复成了 -1。如果你认为这样做更严谨，没有问题：）
但实际上如果没有解，我们也不会访问 pre 了，所以不加是 ok 的。为什么没有解不会访问 pre？如 46 行所示：
继续加油！：）
112021-10-18
相似问题