In this guide, we will explore the process of detecting Hamilton Cycles in C++ through various illustrations.
What is Hamiltonian Cycle?
A Hamiltonian Cycle or Circuit G is a closed loop that visits every single vertex precisely once before reaching back to the initial vertex. A graph earns the title of being Hamiltonian when it possesses a Hamiltonian cycle; in absence of which, it is labeled as non-Hamiltonian.
There is presently no viable resolution accessible for tackling the widely recognized NP-complete issue of locating a Hamiltonian Cycle in a graph across all documented graph variations. However, solutions can be achieved for limited or specific graph categories.
The challenge of finding a Hamiltonian Cycle has practical uses across various fields such as computer science, network planning, and supply chain management.
What do you mean by Hamiltonian Path?
In a graph G, a Hamiltonian Path is a route that traverses every vertex exactly once without needing to return to the initial vertex. Discovering a Hamiltonian Path in a typical graph is known to be NP-complete and can pose challenges, similar to the Hamiltonian Cycle problem. Nonetheless, it is often considered an easier task compared to identifying a Hamiltonian Cycle.
Hamiltonian Paths have various uses such as designing circuits, conducting research in graph theory, and identifying optimal routes within transportation networks.
Backtracking:
Backtracking is a technique used in algorithms to solve problems through recursive processes. It entails constructing solutions step by step and discarding any solutions that do not meet the specified constraints at any given point.
Let's examine the explanation of a Hamiltonian cycle.
Hamiltonian cycle:
To get back to the initial vertex from any starting point, it is necessary to visit all vertices exactly once.
Let's examine the problem now.
Problem Statement:
Let's consider an undirected graph comprising N vertices represented by an N x N adjacency matrix. Our objective is to display all possible Hamiltonian cycles within this graph.
Example:
This is how the provided graph is shown:
The provided graph is depicted using an adjacency matrix.
{ 0, 1, 1, 0, 0, 1 }
{ 1, 0, 1, 0, 1, 1 }
{ 1, 1, 0, 1, 0, 0 }
{ 0, 0, 1, 0, 1, 0 }
{ 0, 1, 0, 1, 0, 1 }
{ 1, 1, 0, 0, 1, 0 }
Output:
0 1 2 3 4 5 0
0 1 5 4 3 2 0
0 2 3 4 1 5 0
0 2 3 4 5 1 0
0 5 1 4 3 2 0
0 5 4 3 2 1 0
By traversing each vertex in the graph once, we can reach the starting point (in this instance, 0) following the path 0->1->2->3->4->5->0. Our findings indicate that this procedure can be repeated through various routes, as detailed in our analysis.
Working mechanism:
The next step is to take the following method in order to print every Hamiltonian cycle in an undirected graph.
- In order to determine whether the vertex being considered at the moment is not already part of the path and is not next to the preceding vertex, we must first build a function.
- The vertex can be safely counted if the first two conditions are met.
- After that, the function to locate all Hamiltonian cycles will be defined. There will be a path from the last vertex to the first vertex and all of the graph's vertices will be present.
- The source vertex will be a part of our path, and the full path will be printed. After printing the path, the source vertex must be removed.
- To find a new path for the upcoming vertices, repeat the aforementioned stages.
- We will print all conceivable Hamiltonian cycles. We will mention that no hamiltonian cycles are feasible if the aforementioned conditions are not met.
To display all Hamiltonian Cycles in an undirected graph, follow this pseudocode:
function isSafe(int vertex, int adjacencyMatrix[6], vector<int> route, int position):
1. If graph[path[pos - 1]][v] == 0:
return false
2. for ( i = 0 to pos)
if (path[i] == v): return false;
3. return true
4. end procedure
function LocateHamiltonianCycle(matrix, position, route, isChecked, size) {
1. if (pos == N):
if (graph[path[path.size() - 1]][path[0]] != 0):
path.push_back(0)
for (i = 0 to path.size()):
cout << path[I] << " "
path.pop_back()
hasCycle = true
return
2. for ( v = 0 to N):
if (isSafe(v, graph, path, pos) && !visited[v]):
path.push_back(v)
visited[v] = true
FindHamCycle(graph, pos + 1, path, visited, N)
visited[v] = false;
path.pop_back()
3. end procedure
procedure hamCycle(int graph[6], int N):
1. hasCycle = false
2. vector<int> path
3. path.push_back(0)
4. bool visited[N]
5. for(i=0 to N):
visited[i] = false
6. visited[0] = true
7. FindHamCycle(graph, 1, path, visited, N)
8. if (!hasCycle): cout << "No Hamiltonian Cycle" << "possible " << endl
9. end procedure
Program:
// C++ program to Print all Hamiltonian Cycles in an Undirected Graph
#include <bits/stdc++.h>
using namespace std;
const int V = 6; // Number of vertices in the graph
void printHamiltonianCycle(int path[], int N) {
cout << "Hamiltonian Cycle: ";
for (int i = 0; i < N; i++) {
cout << path[i] << " ";
}
cout << path[0] << endl;
}
bool isSafe(int v, int pos, int path[], int graph[V][V], bool visited[]) {
if (graph[path[pos - 1]][v] == 0) {
return false;
}
if (visited[v]) {
return false;
}
return true;
}
bool findHamiltonianCycleUtil(int graph[V][V], int path[], int pos, bool visited[]) {
if (pos == V) {
// Check if there's an edge from the last vertex to the first vertex
if (graph[path[pos - 1]][path[0]] == 1) {
printHamiltonianCycle(path, V);
return true;
} else {
return false;
}
}
for (int v = 1; v < V; v++) {
if (isSafe(v, pos, path, graph, visited)) {
path[pos] = v;
visited[v] = true;
if (findHamiltonianCycleUtil(graph, path, pos + 1, visited)) {
return true;
}
path[pos] = -1; // Backtrack
visited[v] = false;
}
}
return false;
}
bool findHamiltonianCycle(int graph[V][V]) {
int path[V];
bool visited[V];
for (int i = 0; i < V; i++) {
path[i] = -1;
visited[i] = false;
}
// Starting from vertex 0
path[0] = 0;
visited[0] = true;
if (!findHamiltonianCycleUtil(graph, path, 1, visited)) {
cout << "No Hamiltonian Cycle possible" << endl;
return false;
}
return true;
}
int main() {
int graph[V][V] = {
{0, 1, 1, 0, 0, 1},
{1, 0, 1, 0, 1, 1},
{1, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 1, 0, 1, 0, 1},
{1, 1, 0, 0, 1, 0},
};
findHamiltonianCycle(graph);
return 0;
}
Output:
Hamiltonian Cycle: 0 1 2 3 4 5 0
Complexity Evaluation
Time Complexity: O(N!).
A total of N! iterations of the matrix are executed, with N representing the total number of nodes within the network.
Space complexity: O(N) .
The number of nodes required for displaying the paths will be N as the graph contains N nodes.
