hamiltonian Algorithm
The Hamiltonian Algorithm is a graph theory-based computational method used to solve the Hamiltonian Cycle problem, which involves finding a path in a given graph that visits each vertex exactly once and returns to the initial vertex, forming a cycle. This algorithm has applications in various fields, such as network routing, scheduling, computer graphics, and even DNA sequencing. The Hamiltonian Algorithm is an important topic in computer science due to its relationship with the theory of NP-completeness, which deals with problems that have no known efficient algorithmic solutions.
There are several approaches to solving the Hamiltonian Cycle problem, including backtracking, dynamic programming, and heuristic methods, but no known efficient algorithm for finding Hamiltonian Cycles in general graphs exists. Backtracking algorithms typically involve constructing a path incrementally and backtracking when a dead-end is reached. Dynamic programming techniques attempt to break the problem down into smaller overlapping subproblems and solve them optimally. Heuristic methods, such as genetic algorithms or simulated annealing, are used to find approximate solutions in a reasonable time. Despite extensive research in this area, the Hamiltonian Cycle problem remains a challenging computational task due to its exponential growth in complexity for large graphs.
#include <stdio.h>
#include <stdbool.h>
#include "Graph.h"
#define MAX_NODES 1000
bool visited[MAX_NODES];
bool hamiltonR(Graph g, int nV, Vertex v, Vertex dest, int d) {
// v = current vertex considered
// dest = destination vertex
// d = distance "remaining" until path found
Vertex w;
if (v == dest) {
return (d == 0);
} else {
visited[v] = true;
for (w = 0; w < nV; w++) {
if (adjacent(g, v, w) && !visited[w]) {
if (hamiltonR(g, nV, w, dest, d-1)) {
return true;
}
}
}
}
visited[v] = false;
return false;
}
bool hasHamiltonianPath(Graph g, int nV, Vertex src, Vertex dest) {
Vertex v;
for (v = 0; v < nV; v++)
visited[v] = false;
return hamiltonR(g, nV, src, dest, nV-1);
}
int main(void) {
Edge e;
int n;
printf("Enter the number of vertices: ");
scanf("%d", &n);
Graph g = newGraph(n);
Vertex src, dest;
printf("Enter source node: ");
scanf("%d", &src);
printf("Enter destination node: ");
scanf("%d", &dest);
printf("Enter an edge (from): ");
while (scanf("%d", &e.v) == 1) {
printf("Enter an edge (to): ");
scanf("%d", &e.w);
insertEdge(g, e);
printf("Enter an edge (from): ");
}
printf("Finished.\n");
printf("The graph has ");
if (hasHamiltonianPath(g, n, src, dest))
printf("a");
else
printf("no");
printf(" Hamiltonian path from %d to %d.\n", src, dest);
freeGraph(g);
return 0;
}
// By
// .----------------. .----------------. .----------------. .-----------------. .----------------. .----------------.
// | .--------------. || .--------------. || .--------------. || .--------------. | | .--------------. || .--------------. |
// | | _________ | || | _____ _____ | || | __ | || | ____ _____ | | | | ____ ____ | || | ____ | |
// | | | _ _ | | || ||_ _||_ _|| || | / \ | || ||_ \|_ _| | | | | |_ || _| | || | .' `. | |
// | | |_/ | | \_| | || | | | | | | || | / /\ \ | || | | \ | | | | | | | |__| | | || | / .--. \ | |
// | | | | | || | | ' ' | | || | / ____ \ | || | | |\ \| | | | | | | __ | | || | | | | | | |
// | | _| |_ | || | \ `--' / | || | _/ / \ \_ | || | _| |_\ |_ | | | | _| | | |_ | || | \ `--' / | |
// | | |_____| | || | `.__.' | || ||____| |____|| || ||_____|\____| | | | | |____||____| | || | `.____.' | |
// | | | || | | || | | || | | | | | | || | | |
// | '--------------' || '--------------' || '--------------' || '--------------' | | '--------------' || '--------------' |
// '----------------' '----------------' '----------------' '----------------' '----------------' '----------------'
// Email : z5261243@unsw.edu.au
// hhoanhtuann@gmail.com
