2020-2021:teams:hotpot:circuit
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:circuit [2020/05/20 21:04] misakatao 更新 |
2020-2021:teams:hotpot:circuit [2020/05/20 21:05] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 163: | 行 163: | ||
| (4) 到此为止，已经构造出来了一个没有重复节点的的回路，如果其长度为N，则哈密顿回路就找到了。如果回路的长度小于$N$，由于整个图是连通的，所以在该回路上，一定存在一点与回路之外的点相邻。那么从该点处把回路断开，就变回了一条路径，同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径，则一定有新的节点被加进来。接着回到步骤(2)。 | (4) 到此为止，已经构造出来了一个没有重复节点的的回路，如果其长度为N，则哈密顿回路就找到了。如果回路的长度小于$N$，由于整个图是连通的，所以在该回路上，一定存在一点与回路之外的点相邻。那么从该点处把回路断开，就变回了一条路径，同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径，则一定有新的节点被加进来。接着回到步骤(2)。 | ||
| + | |||
| + | 时间复杂度为$O(n^2)$。代码可以看[[https://www.cnblogs.com/Ash-ly/p/5452580.html|这篇博客]] | ||
2020-2021/teams/hotpot/circuit.1589979844.txt.gz · 最后更改: 2020/05/20 21:04 由 misakatao
