Scribd
Upload
34 views4 pages

Laboratory Assignment File

The document is a laboratory assignment file for a Design and Analysis of Algorithms course. It includes code to find all Hamiltonian cycles in a graph using backtracking. The code takes a graph as input, uses recursion to try all paths, and outputs any Hamiltonian cycles found.

Uploaded by

Alok Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
34 views4 pages

Laboratory Assignment File

The document is a laboratory assignment file for a Design and Analysis of Algorithms course. It includes code to find all Hamiltonian cycles in a graph using backtracking. The code takes a graph as input, uses recursion to try all paths, and outputs any Hamiltonian cycles found.

Uploaded by

Alok Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Laboratory Assignment File

For

Design And Analysis of Algorithms Laboratory


(CSPC-226)

B.Tech (Computer Science and Engineering)


IV Semester Sec-A

Department of Computer Science and Engineering


DR B R AMBEDKAR NATIONAL INSTITUTE OF
TECHNOLOGY
Jalandhar -144011,Punjab-India

Prepared during (Jan-June 2024) By


Name: ALOK KUMAR
Roll No: 22103010
Assignment-11
Q: WAP to find all patterns of Hamiltonian cycle from the graph given below:

CODE-
#include <iostream>
#include <vector>
using namespace std;

class Graph {
private:
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency matrix

public:
Graph(int V) : V(V), adj(V, vector<int>(V, 0)) {}

void addEdge(int v, int w) {


adj[v][w] = 1;
adj[w][v] = 1;
}

bool isSafe(int v, vector<int>& path, int pos) {


if (adj[path[pos - 1]][v] == 0) {
return false; // No edge between the last added vertex and the
current vertex
}

for (int i = 0; i < pos; i++) {


if (path[i] == v) {
return false; // Vertex already in the path
}
}

return true;
}

bool hamiltonianCycleUtil(vector<int>& path, int pos) {


if (pos == V) {
if (adj[path[pos - 1]][path[0]] == 1) {
return true; // If there's an edge from the last to the first
vertex
} else {
return false;
}
}

for (int v = 1; v < V; v++) {


if (isSafe(v, path, pos)) {
path[pos] = v;
if (hamiltonianCycleUtil(path, pos + 1)) {
return true;
}
path[pos] = -1; // Backtracking
}
}

return false;
}

void hamiltonianCycle() {
std::vector<int> path(V, -1);
path[0] = 0; // Start from vertex 0

if (!hamiltonianCycleUtil(path, 1)) {
std::cout << "No Hamiltonian Cycle found\n";
return;
}

displayCycle(path);
}

void displayCycle(const std::vector<int>& path) {


std::cout << "Hamiltonian Cycle exists: ";
for (int i = 0; i < V; i++) {
std::cout << path[i] << " ";
}
cout << path[0] << endl;
}
};
int main() {
//let a = 0, b = 1 , c = 2 and so on....
// Create a graph given in the above diagram
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 2);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 0);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(4, 2);
g.addEdge(4, 3);
g.addEdge(4, 5);
g.addEdge(4, 1);g.addEdge(5, 3);
g.addEdge(5, 4);

g.hamiltonianCycle();

return 0;
}

OUTPUT-

You might also like