backtracking - graph representation - finding the hamiltonian path
The problem gives you the adjacency matrix and wants you to find the hamiltonian path.
First, since the graph is dense the hamiltonian path exists( I think so ), so for all test cases you have an answer to this problem, and since the order is not important your path can start from node 1 and end at node 1.
What you have to do is to construct just a path from node 1 that ends up in a node which is adjacent to node 1, so you can print the path at that time.
I use a 2-dimensional array for adjacency matrix, a boolean array for marking nodes, because each node can be traversed once except node 1 which is the start and the end of the path, and an array of integers for saving the order of the nodes I'm visiting.
I start backtracking from node 1 and each time in the function I check whether there exist another node which is not visited and continue backtracking with this node.
As backtracking goes on, sometime I find out that I have visited all nodes once and that's the time I print the path and that's it.
No comments:
Post a Comment