I was looking for some hamiltonian cycle algorithms, but I can't find any implementations, not even a single pseudo-code ! I don't even need to output the cycle, just check if the graph has one. The input is a graph with V vertices and E edges. Also, I would like to have an algorithm to check if a graph has a hamiltonian path. I don't need to output the path, just check if it has one. Both should be in polynomial time.
The problem is one of the NP-Complete problems.
A brute force algorithm is just creating all permutations and checking if one of them is feasible solution.
Checking the feasibility:
let the current permutation be v1,v2,...,vn: if for each i there is an edge v_i -> v_(i+1) in the graph, and also v_n->v1 - then the solution is feasible.
An alternative is creating a graph G'=(V,E',w) where the new edges E' = VxV (all edges) and the weight function is:
w(u,v) = 1 if there is an edge (u,v) in the original graph
infinity otherwise.
Now you got yourself a Traveling-salesman problem, and can solve it with dynamic programming in O(n^2*2^n)