#include <stdio.
h>
#include <stdlib.h>
#include <time.h>
#define MAX 100
int numVertices, nodeCount = 0, solutionCount = 0;
int graph[MAX][MAX], path[MAX];
int adj[MAX][MAX], adjCount[MAX];
struct TreeNode {
int id, level, vertex, isValid, childCount, maxChildren;
struct TreeNode *parent;
struct TreeNode **children;
};
struct TreeNode* createNode(int level, int vertex, int isValid) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (!newNode) {
printf("Memory allocation failed!\n");
exit(1);
}
nodeCount++;
newNode->id = nodeCount;
newNode->level = level;
newNode->vertex = vertex;
newNode->isValid = isValid;
newNode->parent = NULL;
newNode->children = NULL;
newNode->childCount = 0;
newNode->maxChildren = 0;
return newNode;
}
void addChild(struct TreeNode* parent, struct TreeNode* child) {
if (parent->childCount >= parent->maxChildren) {
int newSize = parent->maxChildren == 0 ? 4 : parent->maxChildren * 2;
parent->children = realloc(parent->children, newSize * sizeof(struct
TreeNode*));
if (!parent->children) {
printf("Memory allocation failed!\n");
exit(1);
}
parent->maxChildren = newSize;
}
parent->children[parent->childCount++] = child;
child->parent = parent;
}
void printIndent(int spaces) {
int i;
for (i = 0; i < spaces; i++) {
printf(" ");
}
}
void printTree(struct TreeNode* node, int depth) {
int i;
if (!node) return;
for (i = 0; i < node->childCount; i++) {
if (node->children[i]->vertex < node->vertex)
printTree(node->children[i], depth + 1);
}
printIndent(depth);
if (node->level == numVertices && node->isValid)
printf("%d SOLUTION\n", node->vertex);
else if (node->isValid)
printf("%d\n", node->vertex);
else
printf("%d (B)\n", node->vertex);
for (i = 0; i < node->childCount; i++) {
if (node->children[i]->vertex >= node->vertex)
printTree(node->children[i], depth + 1);
}
}
void freeTree(struct TreeNode* node) {
int i;
if (!node) return;
for (i = 0; i < node->childCount; i++) {
freeTree(node->children[i]);
}
if (node->children)
free(node->children);
free(node);
}
int isNextVertexValid(int level, int vertex) {
int j;
if (!graph[path[level - 1]][vertex]) return 0;
for (j = 1; j < level; j++) {
if (path[j] == vertex) return 0;
}
if (level == numVertices && !graph[vertex][path[1]]) return 0;
return 1;
}
struct TreeNode* findHamiltonian(int level, struct TreeNode* parent) {
int i, previousVertex = path[level - 1];
struct TreeNode* rootNode = NULL;
for (i = 0; i < adjCount[previousVertex]; i++) {
int currentVertex = adj[previousVertex][i];
path[level] = currentVertex;
int valid = isNextVertexValid(level, currentVertex);
struct TreeNode* childNode = createNode(level, currentVertex, valid);
if (parent)
addChild(parent, childNode);
else
rootNode = childNode;
if (valid) {
if (level == numVertices) {
printf("Solution %d: ", ++solutionCount);
int j;
for (j = 1; j <= numVertices; j++) {
printf("%d -> ", path[j]);
}
printf("%d\n", path[1]);
} else {
findHamiltonian(level + 1, childNode);
}
}
}
return rootNode;
}
int main() {
int u, v, i;
clock_t start, end;
double timeTaken;
for (i = 0; i < MAX; i++) {
adjCount[i] = 0;
}
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);
printf("Enter the edges (format: u v), enter -1 -1 to stop:\n");
while (1) {
scanf("%d %d", &u, &v);
if (u == -1 && v == -1) break;
if (u < 1 || v < 1 || u > numVertices || v > numVertices) {
printf("Invalid edge!\n");
} else {
graph[u][v] = 1;
graph[v][u] = 1;
adj[u][adjCount[u]++] = v;
adj[v][adjCount[v]++] = u;
}
}
path[1] = 1; // Start from vertex 1
struct TreeNode* root = createNode(1, 1, 1);
printf("\nHamiltonian Cycles:\n");
start = clock();
findHamiltonian(2, root);
end = clock();
printf("\nState Space Tree:\n");
printTree(root, 0);
timeTaken = ((double)(end - start)) * 1000.0 / CLOCKS_PER_SEC;
printf("\nTime Taken: %.6f milliseconds\n", timeTaken);
freeTree(root);
return 0;
}
