Hamiltonian circuit

[Dain1234]

include

define NODE 4

using namespace std;

int graph[NODE][NODE]; int path[NODE];

void displayCycle() {
cout<<"The Hamilton Cycle : " << endl;

for (int i = 0; i < NODE; i++) cout << path[i] << " "; cout << path[0] << endl;
}

bool isValid(int v, int k) { if (graph [path[k-1]][v] == 0)
return false;

for (int i = 0; i < k; i++)
if (path[i] == v) return false; return true; }

bool cycleFound(int k) { if (k == NODE) {
if (graph[path[k-1]][ path[0] ] == 1 ) return true; else return false; }

for (int v = 1; v < NODE; v++) {
if (isValid(v,k)) {
path[k] = v; if (cycleFound (k+1) == true) return true; path[k] = -1;
} } return false; }

bool hamiltonianCycle() { for (int i = 0; i < NODE; i++) path[i] = -1; path[0] = 0;

if ( cycleFound(1) == false ) { cout << "Solution does not exist"<<endl; return false; }

displayCycle(); return true; }

int main() { int i,j; cout << "Enter the Graph : " << endl; for (i=0;i<NODE;i++){ for (j=0;j<NODE;j++){ cout << "Graph G(" << (i+1) << "," << (j+1) << ") = "; cin >> graph[i][j]; } } cout << endl; cout << "The Graph :" << endl; for (i=0;i<NODE;i++){ for (j=0;j<NODE;j++){ cout << graph [i][j] << "\t"; } cout << endl; }

cout << endl;

hamiltonianCycle();

}

[Dain1234]

Enter the Graph : Graph G(1,1) = 3 Graph G(1,2) = 6 Graph G(1,3) = 9 Graph G(1,4) = 10 Graph G(2,1) = 12 Graph G(2,2) = 14 Graph G(2,3) = 16 Graph G(2,4) = 2 Graph G(3,1) = 4 Graph G(3,2) = 8 Graph G(3,3) = 5 Graph G(3,4) = 12 Graph G(4,1) = 14 Graph G(4,2) = 16 Graph G(4,3) = 19 Graph G(4,4) = 20

The Graph : 3 6 9 10 12 14 16 2 4 8 5 12 14 16 19 20

Solution does not exist