Python: Solve a Hamiltonian Path using a Brute Force Iterative Algorithm -- 2
Budget: $10 ā $30 USD
I want a hamiltonian path problem solved using a brute force iterative algorithm.
The program will read in a representation of a graph from a plain text file with the following format: the
first line is n, the number of vertices in G which are numbered 0 through nā1. Each line
after that contains a sequence of space-delimited numbers. The first number is a vertex
v and each following number is a vertex that v is connected to. This is an undirected
graph so the symmetric edges may or may not be present in the representation. An
example is provided below.
9
0 3 1
1 4 0 2
2 5 1
3 0 6 4
4 1 7 3 5
5 2 8 4
6 3 7
7 4 6 8
8 5 7
The program will accept a file name from the command line arguments, parse the
graph representation and determine whether or not there is a Hamiltonian path in the
graph. If not, your program will output No Hamiltonian Path otherwise it will output
a sequence of vertex numbers that represent a Hamiltonian path. Note that there could
be multiple Hamiltonian paths so your output might find a different Hamiltonian path.
For the example above, one such solution could be:
Hamiltonian Path: 0 3 4 1 2 5 8 7 6
The program will read in a representation of a graph from a plain text file with the following format: the
first line is n, the number of vertices in G which are numbered 0 through nā1. Each line
after that contains a sequence of space-delimited numbers. The first number is a vertex
v and each following number is a vertex that v is connected to. This is an undirected
graph so the symmetric edges may or may not be present in the representation. An
example is provided below.
9
0 3 1
1 4 0 2
2 5 1
3 0 6 4
4 1 7 3 5
5 2 8 4
6 3 7
7 4 6 8
8 5 7
The program will accept a file name from the command line arguments, parse the
graph representation and determine whether or not there is a Hamiltonian path in the
graph. If not, your program will output No Hamiltonian Path otherwise it will output
a sequence of vertex numbers that represent a Hamiltonian path. Note that there could
be multiple Hamiltonian paths so your output might find a different Hamiltonian path.
For the example above, one such solution could be:
Hamiltonian Path: 0 3 4 1 2 5 8 7 6