如何在图中找到哈密尔顿周期

本文介绍了如何在图中找到哈密尔顿周期的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我试图解决哈密尔顿周期问题。我能够找到所有顶点的路径，但无法完成周期。

有人可以提供一个算法来找到这个循环吗？

解决方案

确定一个图是否有哈密尔顿周期一个NP完全问题。这意味着我们可以检查给定路径是否为多项式时间内的哈密尔顿循环，但我们不知道任何能够找到的多项式时间算法。

可用于查找哈密尔顿循环的唯一算法是指数时间算法。其中一些是

• 蛮力搜索
• 动态编程
• 您可以在此处找到其他指数级但速度更快的算法
ul>

I am trying to solve the Hamiltonian Cycle problem. I am able to find a path with all the vertices, but unable to complete the cycle.

Can someone provide me with an algorithm to find the cycle?

解决方案

Determining if a graph has a Hamiltonian Cycle is a NP-complete problem. This means that we can check if a given path is a Hamiltonian cycle in polynomial time, but we don't know any polynomial time algorithms capable of finding it.

The only algorithms that can be used to find a Hamiltonian cycle are exponential time algorithms. Some of them are

• Brute force search
• Dynamic programming
• Other exponential but nevertheless faster algorithms that you can find here