Can someone introduce me to the Hamiltonian Cycle?

I have this project where I have to come up with Java source code imple开发者_如何学Gomenting the Hamiltonian cycle. I searched on google and at least now I know what a Hamiltonian cycle is, path that passes through all vertices just once except the starting vertex because it's also the last vertex (tell me if I'm wrong). The problem is I don't know how to implement it. Basically, my questions are:

1. How, where do you implement a Hamiltonian cycle?
2. What is the application of a Hamiltonian Cycle (so that it helps to understand why it's so important)

---

1. You don't implement a Hamiltonian cycle, you find it (or find out that none exists for your given graph). Since this is an NP-complete problem, which means this is probably no efficient solution, I'd just implement a simple backtracking algorithm. Since you're looking for a cycle, it does not matter at which node you start.
2. Hamiltonian cycles can be used in cryptography for zero-knowledge proofs. I'm not sure whether this is still just research or whether it's being actively used in any cryptographic protocol.

---

Is this homework? If so please tag it as such.

It is easy to implement it if you can use recursion (not the case if the graph gets too large). What you do is write a function that takes as argument the graph (there are different representations for this), the function checks whether the graph consists of only the starting-point, if so it returns, if it didnt return it calls itself recursively for each node N that is still in the graph and gives the graph minus the node N as arguments.

---

The simplest way is to start with one node, "tag it", choose the next reachable "untagged" node, "tag it", and continue until either:

• you reach the starting node, thus you found Hamiltonian cycle. Repeat the cycle for every node to find each and every Hamiltonian cycle in that graph.
• You cannot choose another "untagged" node, which means that there is no Hamiltonian cycle for that starting node (but you found a Hamiltonian Path, anyway).

That algorithm can be optimized in several ways, but I let you that to you. Any solution you find will be NP-complete.

As for they uses, I only saw them in Graph theory and AI classes (this is a particular travelsman problem, where each edge has a cost of 1) and they never told me real-life uses for that.

---

(B) Practical Application

• Determining most efficient switching network for phone systems
• Best bus routes, postal routes, meter checking routes