Print all Hamiltonian path present in a graph

The Hamiltonian path problem is a well-known problem in graph theory. It deals with finding a path in a graph that visits every vertex exactly once. In this article, we will discuss how to print all Hamiltonian paths present in a graph using a simple algorithm.

Problem Statement

Given a graph with `V` vertices, we want to find and print all the Hamiltonian paths present in the graph. A Hamiltonian path is a path that visits every vertex exactly once and returns to the starting vertex.

Let's consider an example graph:

```    0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1‒‒‒│‒‒‒‒‒‒‒│‒‒4
│╲  │       │ ╱
│ ╲ │       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
```

In the above graph, we can see that there are multiple Hamiltonian paths possible. Our goal is to find and print all these paths.

Pseudocode Algorithm

To solve this problem, we will use a backtracking algorithm that explores all possible paths in the graph. Here is the pseudocode for the algorithm:

```function printSolution(solution[], size):
for i from 0 to size:
print solution[i]

function findSolution(graph[][], visited[], result[], node, start, counter):
if counter = V and node = start:
result[counter] = node
printSolution(result, V+1)

if counter >= V or visited[node] ≠ -1:
return

visited[node] = 1
result[counter] = node

for i from 0 to V:
if graph[node][i] = 1:
findSolution(graph, visited, result, i, start, counter+1)

visited[node] = -1

function setDefault(visited[]):
for i from 0 to V:
visited[i] = -1

function hamiltonianCycle(graph[][]):
visited[V]
result[V+1]

for i from 0 to V:
setDefault(visited)
findSolution(graph, visited, result, i, i, 0)
```

The `printSolution` function is responsible for printing the Hamiltonian path. The `findSolution` function recursively explores all possible paths in the graph, while keeping track of visited nodes and storing the current path in the `result` array. The `setDefault` function initializes the `visited` array, and the `hamiltonianCycle` function handles the request of finding all Hamiltonian paths in the graph.

Program Solution

``````// C Program
// Print all Hamiltonian path present in a graph

#include <stdio.h>
#define V 6
// Print the solution of Hamiltonian Cycle
void printSolution(int solution[],int size)
{

for (int i = 0; i < size; ++i)
{
printf("  %d",solution[i]);
}
printf("\n");
}

// Detect  hamiltonian path exists in this graph or not
void findSolution(int graph[V][V], int visited[],int result[],int node,int start, int counter)
{

if(counter==V && node == start)
{
result[counter] = node;
printSolution(result,V+1);
}

if(counter >= V ||  visited[node] != -1)
{
// When node is already visited or
// node size is greater than graph node
return ;
}
// indicates visiting node
visited[node] = 1;

// Store path result
result[counter] = node;

for (int i = 0; i < V; ++i)
{
if(graph[node][i]==1)
{
findSolution(graph,visited,result,i,start,counter+1);
}

}
// reset the status of visiting node
visited[node] = -1;

}

void setDefault(int visited[])
{

for (int i = 0; i < V; ++i)
{
visited[i] = -1;

}

}
// Handles the request of finding hamiltonian path
void hamiltonianCycle(int graph[V][V])
{

// Indicator of visited node
int visited[V];

// Used to store path information
int result[V+1];
printf("\n  Hamiltonian Cycle \n");
for (int i = 0; i < V; ++i)
{
setDefault(visited);
findSolution(graph,visited,result,i,i,0);
}

}

int main(int argc, char const *argv[])
{

/*

0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1‒‒‒│‒‒‒‒‒‒‒│‒‒4
│╲  │       │ ╱
│ ╲ │       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/

int graph[V][V] =
{
{0, 0, 1, 0, 0, 1},
{0, 0, 1, 1, 1, 0},
{1, 1, 0, 1, 0, 0},
{0, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{1, 0, 0, 1, 1, 0}
};
hamiltonianCycle(graph);

return 0;
}``````

Output

``````  Hamiltonian Cycle
0  2  1  3  4  5  0
0  2  1  4  3  5  0
0  2  3  1  4  5  0
0  5  3  4  1  2  0
0  5  4  1  3  2  0
0  5  4  3  1  2  0
1  2  0  5  3  4  1
1  2  0  5  4  3  1
1  3  2  0  5  4  1
1  3  4  5  0  2  1
1  4  3  5  0  2  1
1  4  5  0  2  3  1
2  0  5  3  4  1  2
2  0  5  4  1  3  2
2  0  5  4  3  1  2
2  1  3  4  5  0  2
2  1  4  3  5  0  2
2  3  1  4  5  0  2
3  1  2  0  5  4  3
3  1  4  5  0  2  3
3  2  0  5  4  1  3
3  4  1  2  0  5  3
3  4  5  0  2  1  3
3  5  0  2  1  4  3
4  1  2  0  5  3  4
4  1  3  2  0  5  4
4  3  1  2  0  5  4
4  3  5  0  2  1  4
4  5  0  2  1  3  4
4  5  0  2  3  1  4
5  0  2  1  3  4  5
5  0  2  1  4  3  5
5  0  2  3  1  4  5
5  3  4  1  2  0  5
5  4  1  3  2  0  5
5  4  3  1  2  0  5``````
``````/*
Java Program for
Print all Hamiltonian path present in a graph
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
public void printSolution(int[] solution, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("   " + solution[i]);
}
System.out.print("\n");
}
// Detect  hamiltonian path exists in this graph or not
public void findSolution(int[][] graph, boolean[] visited, int[] result, int node, int counter, int n, int start)
{
if (counter == n && node == start)
{
result[counter] = node;
printSolution(result, n + 1);
}
if (visited[node] == true)
{
return;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (int i = 0; i < n; ++i)
{
if (graph[node][i] == 1)
{
findSolution(graph, visited, result, i, counter + 1, n, start);
}
}
// reset the status of visiting node
visited[node] = false;
}
void setDefault(boolean visited[], int n)
{
for (int i = 0; i < n; ++i)
{
visited[i] = false;
}
}
// Handles the request of find and display hamiltonian path
public void hamiltonianCycle(int[][] graph, int n)
{
// Indicator of visited node
boolean[] visited = new boolean[n];
// Used to store path information
int[] result = new int[n + 1];
System.out.print("\n   Hamiltonian Cycle \n");
for (int i = 0; i < n; ++i)
{
setDefault(visited, n);
findSolution(graph, visited, result, i, 0, n, i);
}
}
public static void main(String[] args)
{
/*

0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
int[][] graph =
{
{ 0 , 0 , 1 , 0 , 0 , 1 } ,
{ 0 , 0 , 1 , 1 , 1 , 0 } ,
{ 1 , 1 , 0 , 1 , 0 , 0 } ,
{ 0 , 1 , 1 , 0 , 1 , 1 } ,
{ 0 , 1 , 0 , 1 , 0 , 1 } ,
{ 1 , 0 , 0 , 1 , 1 , 0 }
};
// Number of graph node
int n = graph.length;
}
}``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5``````
``````// Include header file
#include <iostream>
#define V 6
using namespace std;
/*
C++ Program for
Print all Hamiltonian path present in a graph
*/
class GraphCycle
{
public:
// Print the solution of Hamiltonian Cycle
void printSolution(int solution[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "   " << solution[i];
}
cout << "\n";
}
// Detect  hamiltonian path exists in this graph or not
void findSolution(int graph[V][V], bool visited[], int result[], int node, int counter, int n, int start)
{
if (counter == n && node == start)
{
result[counter] = node;
this->printSolution(result, n + 1);
}
if (visited[node] == true)
{
return;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (int i = 0; i < n; ++i)
{
if (graph[node][i] == 1)
{
this->findSolution(graph, visited, result, i, counter + 1, n, start);
}
}
// reset the status of visiting node
visited[node] = false;
}
void setDefault(bool visited[] , int n)
{
for (int i = 0; i < n; ++i)
{
visited[i] = false;
}
}
// Handles the request of find and display hamiltonian path
void hamiltonianCycle(int graph[V][V], int n)
{
// Indicator of visited node
bool visited[n];
// Used to store path information
int result[n + 1];
cout << "\n   Hamiltonian Cycle \n";
for (int i = 0; i < n; ++i)
{
this->setDefault(visited, n);
this->findSolution(graph, visited, result, i, 0, n, i);
}
}
};
int main()
{
/*

0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
int graph[V][V] =
{
{0, 0, 1, 0, 0, 1},
{0, 0, 1, 1, 1, 0},
{1, 1, 0, 1, 0, 0},
{0, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{1, 0, 0, 1, 1, 0}
};
return 0;
}``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5``````
``````// Include namespace system
using System;
/*
C# Program for
Print all Hamiltonian path present in a graph
*/
public class GraphCycle
{
// Print the solution of Hamiltonian Cycle
public void printSolution(int[] solution, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write("   " + solution[i]);
}
Console.Write("\n");
}
// Detect  hamiltonian path exists in this graph or not
public void findSolution(int[,] graph, Boolean[] visited, int[] result, int node, int counter, int n, int start)
{
if (counter == n && node == start)
{
result[counter] = node;
printSolution(result, n + 1);
}
if (visited[node] == true)
{
return;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (int i = 0; i < n; ++i)
{
if (graph[node,i] == 1)
{
findSolution(graph, visited, result, i, counter + 1, n, start);
}
}
// reset the status of visiting node
visited[node] = false;
}
void setDefault(Boolean []visited, int n)
{
for (int i = 0; i < n; ++i)
{
visited[i] = false;
}
}
// Handles the request of find and display hamiltonian path
public void hamiltonianCycle(int[,] graph, int n)
{
// Indicator of visited node
Boolean[] visited = new Boolean[n];
// Used to store path information
int[] result = new int[n + 1];
Console.Write("\n   Hamiltonian Cycle \n");
for (int i = 0; i < n; ++i)
{
setDefault(visited, n);
findSolution(graph, visited, result, i, 0, n, i);
}
}
public static void Main(String[] args)
{
/*

0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
int[,] graph =
{
{ 0 , 0 , 1 , 0 , 0 , 1 } ,
{ 0 , 0 , 1 , 1 , 1 , 0 } ,
{ 1 , 1 , 0 , 1 , 0 , 0 } ,
{ 0 , 1 , 1 , 0 , 1 , 1 } ,
{ 0 , 1 , 0 , 1 , 0 , 1 } ,
{ 1 , 0 , 0 , 1 , 1 , 0 }
};
// Number of graph node
int n = graph.GetLength(0);
}
}``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5``````
``````<?php
/*
Php Program for
Print all Hamiltonian path present in a graph
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
public	function printSolution( & \$solution, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "   ". \$solution[\$i];
}
echo "\n";
}
// Detect  hamiltonian path exists in this graph or not
public	function findSolution( & \$graph, & \$visited, & \$result, \$node, \$counter, \$n, \$start)
{
if (\$counter == \$n && \$node == \$start)
{
\$result[\$counter] = \$node;
\$this->printSolution(\$result, \$n + 1);
}
if (\$visited[\$node] == true)
{
return;
}
// indicates visiting node
\$visited[\$node] = true;
// Store path result
\$result[\$counter] = \$node;
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$graph[\$node][\$i] == 1)
{
\$this->findSolution(\$graph, \$visited, \$result, \$i, \$counter + 1, \$n, \$start);
}
}
// reset the status of visiting node
\$visited[\$node] = false;
}

function setDefault( & \$visited, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
\$visited[\$i] = false;
}
}
// Handles the request of find and display hamiltonian path
public	function hamiltonianCycle( & \$graph, \$n)
{
// Indicator of visited node
\$visited = array_fill(0, \$n, false);
// Used to store path information
\$result = array_fill(0, \$n + 1, 0);
echo "\n   Hamiltonian Cycle \n";
for (\$i = 0; \$i < \$n; ++\$i)
{
\$this->setDefault(\$visited, \$n);
\$this->findSolution(\$graph, \$visited, \$result, \$i, 0, \$n, \$i);
}
}
}

function main()
{
/*

0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
\$graph = array(
array(0, 0, 1, 0, 0, 1),
array(0, 0, 1, 1, 1, 0),
array(1, 1, 0, 1, 0, 0),
array(0, 1, 1, 0, 1, 1),
array(0, 1, 0, 1, 0, 1),
array(1, 0, 0, 1, 1, 0)
);
// Number of graph node
\$n = count(\$graph);
}
main();``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5``````
``````/*
Node Js Program for
Print all Hamiltonian path present in a graph
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
printSolution(solution, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("   " + solution[i]);
}
process.stdout.write("\n");
}
// Detect  hamiltonian path exists in this graph or not
findSolution(graph, visited, result, node, counter, n, start)
{
if (counter == n && node == start)
{
result[counter] = node;
this.printSolution(result, n + 1);
}
if (visited[node] == true)
{
return;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (var i = 0; i < n; ++i)
{
if (graph[node][i] == 1)
{
this.findSolution(graph, visited, result, i, counter + 1, n, start);
}
}
// reset the status of visiting node
visited[node] = false;
}
setDefault(visited, n)
{
for (var i = 0; i < n; ++i)
{
visited[i] = false;
}
}
// Handles the request of find and display hamiltonian path
hamiltonianCycle(graph, n)
{
// Indicator of visited node
var visited = Array(n).fill(false);
// Used to store path information
var result = Array(n + 1).fill(0);
process.stdout.write("\n   Hamiltonian Cycle \n");
for (var i = 0; i < n; ++i)
{
this.setDefault(visited, n);
this.findSolution(graph, visited, result, i, 0, n, i);
}
}
}

function main()
{
/*

0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
var graph = [
[0, 0, 1, 0, 0, 1] ,
[0, 0, 1, 1, 1, 0] ,
[1, 1, 0, 1, 0, 0] ,
[0, 1, 1, 0, 1, 1] ,
[0, 1, 0, 1, 0, 1] ,
[1, 0, 0, 1, 1, 0]
];
// Number of graph node
var n = graph.length;
}
main();``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5``````
``````#   Python 3 Program for
#   Print all Hamiltonian path present in a graph

class GraphCycle :
#  Print the solution of Hamiltonian Cycle
def printSolution(self, solution, size) :
i = 0
while (i < size) :
print("   ", solution[i], end = "")
i += 1

print(end = "\n")

#  Detect  hamiltonian path exists in this graph or not
def findSolution(self, graph, visited, result, node, counter, n, start) :
if (counter == n and node == start) :
result[counter] = node
self.printSolution(result, n + 1)

if (visited[node] == True) :
return

#  indicates visiting node
visited[node] = True
#  Store path result
result[counter] = node
i = 0
while (i < n) :
if (graph[node][i] == 1) :
self.findSolution(graph, visited, result, i, counter + 1, n, start)

i += 1

#  reset the status of visiting node
visited[node] = False

def setDefault(self, visited, n) :
i = 0
while (i < n) :
visited[i] = False
i += 1

#  Handles the request of find and display hamiltonian path
def hamiltonianCycle(self, graph, n) :
#  Indicator of visited node
visited = [False] * (n)
#  Used to store path information
result = [0] * (n + 1)
print("\n    Hamiltonian Cycle ")
i = 0
while (i < n) :
self.setDefault(visited, n)
self.findSolution(graph, visited, result, i, 0, n, i)
i += 1

def main() :
#
#         0‒‒‒‒‒‒ 5
#         │       │╲
#         │       │ ╲
#     1 ‒‒│‒‒‒‒‒‒‒│‒‒4
#     │ ╲ │       │ ╱
#     │  ╲│       │╱
#     │   2‒‒‒‒‒‒‒3
#     │           │
#     └‒‒‒‒‒‒‒‒‒‒‒┘
#     ----------------
#         graph
#     ----------------

#  Adjacency matrix of a graph
graph = [
[0, 0, 1, 0, 0, 1] ,
[0, 0, 1, 1, 1, 0] ,
[1, 1, 0, 1, 0, 0] ,
[0, 1, 1, 0, 1, 1] ,
[0, 1, 0, 1, 0, 1] ,
[1, 0, 0, 1, 1, 0]
]
#  Number of graph node
n = len(graph)

if __name__ == "__main__": main()``````

Output

``````    Hamiltonian Cycle
0    2    1    3    4    5    0
0    2    1    4    3    5    0
0    2    3    1    4    5    0
0    5    3    4    1    2    0
0    5    4    1    3    2    0
0    5    4    3    1    2    0
1    2    0    5    3    4    1
1    2    0    5    4    3    1
1    3    2    0    5    4    1
1    3    4    5    0    2    1
1    4    3    5    0    2    1
1    4    5    0    2    3    1
2    0    5    3    4    1    2
2    0    5    4    1    3    2
2    0    5    4    3    1    2
2    1    3    4    5    0    2
2    1    4    3    5    0    2
2    3    1    4    5    0    2
3    1    2    0    5    4    3
3    1    4    5    0    2    3
3    2    0    5    4    1    3
3    4    1    2    0    5    3
3    4    5    0    2    1    3
3    5    0    2    1    4    3
4    1    2    0    5    3    4
4    1    3    2    0    5    4
4    3    1    2    0    5    4
4    3    5    0    2    1    4
4    5    0    2    1    3    4
4    5    0    2    3    1    4
5    0    2    1    3    4    5
5    0    2    1    4    3    5
5    0    2    3    1    4    5
5    3    4    1    2    0    5
5    4    1    3    2    0    5
5    4    3    1    2    0    5``````
``````#   Ruby Program for
#   Print all Hamiltonian path present in a graph

class GraphCycle
#  Print the solution of Hamiltonian Cycle
def printSolution(solution, size)
i = 0
while (i < size)
print("   ", solution[i])
i += 1
end

print("\n")
end

#  Detect  hamiltonian path exists in this graph or not
def findSolution(graph, visited, result, node, counter, n, start)
if (counter == n && node == start)
result[counter] = node
self.printSolution(result, n + 1)
end

if (visited[node] == true)
return
end

#  indicates visiting node
visited[node] = true
#  Store path result
result[counter] = node
i = 0
while (i < n)
if (graph[node][i] == 1)
self.findSolution(graph, visited, result, i, counter + 1, n, start)
end

i += 1
end

#  reset the status of visiting node
visited[node] = false
end

def setDefault(visited, n)
i = 0
while (i < n)
visited[i] = false
i += 1
end

end

#  Handles the request of find and display hamiltonian path
def hamiltonianCycle(graph, n)
#  Indicator of visited node
visited = Array.new(n) {false}
#  Used to store path information
result = Array.new(n + 1) {0}
print("\n   Hamiltonian Cycle \n")
i = 0
while (i < n)
self.setDefault(visited, n)
self.findSolution(graph, visited, result, i, 0, n, i)
i += 1
end

end

end

def main()
#
#         0‒‒‒‒‒‒ 5
#         │       │╲
#         │       │ ╲
#     1 ‒‒│‒‒‒‒‒‒‒│‒‒4
#     │ ╲ │       │ ╱
#     │  ╲│       │╱
#     │   2‒‒‒‒‒‒‒3
#     │           │
#     └‒‒‒‒‒‒‒‒‒‒‒┘
#     ----------------
#         graph
#     ----------------

#  Adjacency matrix of a graph
graph = [
[0, 0, 1, 0, 0, 1] ,
[0, 0, 1, 1, 1, 0] ,
[1, 1, 0, 1, 0, 0] ,
[0, 1, 1, 0, 1, 1] ,
[0, 1, 0, 1, 0, 1] ,
[1, 0, 0, 1, 1, 0]
]
#  Number of graph node
n = graph.length
end

main()``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5
``````
``````/*
Scala Program for
Print all Hamiltonian path present in a graph
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
def printSolution(solution: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("   " + solution(i));
i += 1;
}
print("\n");
}
// Detect  hamiltonian path exists in this graph or not
def findSolution(graph: Array[Array[Int]], visited: Array[Boolean], result: Array[Int], node: Int, counter: Int, n: Int, start: Int): Unit = {
if (counter == n && node == start)
{
result(counter) = node;
this.printSolution(result, n + 1);
}
if (visited(node) == true)
{
return;
}
// indicates visiting node
visited(node) = true;
// Store path result
result(counter) = node;
var i: Int = 0;
while (i < n)
{
if (graph(node)(i) == 1)
{
this.findSolution(graph, visited, result, i, counter + 1, n, start);
}
i += 1;
}
// reset the status of visiting node
visited(node) = false;
}
def setDefault(visited: Array[Boolean], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
visited(i) = false;
i += 1;
}
}
// Handles the request of find and display hamiltonian path
def hamiltonianCycle(graph: Array[Array[Int]], n: Int): Unit = {
// Indicator of visited node
var visited: Array[Boolean] = Array.fill[Boolean](n)(false);
// Used to store path information
var result: Array[Int] = Array.fill[Int](n + 1)(0);
print("\n   Hamiltonian Cycle \n");
var i: Int = 0;
while (i < n)
{
this.setDefault(visited, n);
this.findSolution(graph, visited, result, i, 0, n, i);
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: GraphCycle = new GraphCycle();
/*
0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
var graph: Array[Array[Int]] = Array(
Array(0, 0, 1, 0, 0, 1),
Array(0, 0, 1, 1, 1, 0),
Array(1, 1, 0, 1, 0, 0),
Array(0, 1, 1, 0, 1, 1),
Array(0, 1, 0, 1, 0, 1),
Array(1, 0, 0, 1, 1, 0)
);
// Number of graph node
var n: Int = graph.length;
}
}``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5``````
``````/*
Swift 4 Program for
Print all Hamiltonian path present in a graph
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
func printSolution(_ solution: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("   ", solution[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Detect  hamiltonian path exists in this graph or not
func findSolution(_ graph: [[Int]], _ visited: inout[Bool], _ result: inout[Int], _ node: Int, _ counter: Int, _ n: Int, _ start: Int)
{
if (counter == n && node == start)
{
result[counter] = node;
self.printSolution(result, n + 1);
}
if (visited[node] == true)
{
return;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
var i: Int = 0;
while (i < n)
{
if (graph[node][i] == 1)
{
self.findSolution(graph, &visited, &result, i, counter + 1, n, start);
}
i += 1;
}
// reset the status of visiting node
visited[node] = false;
}
func setDefault(_ visited: inout[Bool], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
visited[i] = false;
i += 1;
}
}
// Handles the request of find and display hamiltonian path
func hamiltonianCycle(_ graph: [
[Int]
], _ n: Int)
{
// Indicator of visited node
var visited: [Bool] = Array(repeating: false, count: n);
// Used to store path information
var result: [Int] = Array(repeating: 0, count: n + 1);
print("\n   Hamiltonian Cycle ");
var i: Int = 0;
while (i < n)
{
self.setDefault(&visited, n);
self.findSolution(graph, &visited, &result, i, 0, n, i);
i += 1;
}
}
}
func main()
{
/*
0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
let graph: [
[Int]
] = [
[0, 0, 1, 0, 0, 1] , [0, 0, 1, 1, 1, 0] , [1, 1, 0, 1, 0, 0] , [0, 1, 1, 0, 1, 1] , [0, 1, 0, 1, 0, 1] , [1, 0, 0, 1, 1, 0]
];
// Number of graph node
let n: Int = graph.count;
}
main();``````

Output

``````   Hamiltonian Cycle
0    2    1    3    4    5    0
0    2    1    4    3    5    0
0    2    3    1    4    5    0
0    5    3    4    1    2    0
0    5    4    1    3    2    0
0    5    4    3    1    2    0
1    2    0    5    3    4    1
1    2    0    5    4    3    1
1    3    2    0    5    4    1
1    3    4    5    0    2    1
1    4    3    5    0    2    1
1    4    5    0    2    3    1
2    0    5    3    4    1    2
2    0    5    4    1    3    2
2    0    5    4    3    1    2
2    1    3    4    5    0    2
2    1    4    3    5    0    2
2    3    1    4    5    0    2
3    1    2    0    5    4    3
3    1    4    5    0    2    3
3    2    0    5    4    1    3
3    4    1    2    0    5    3
3    4    5    0    2    1    3
3    5    0    2    1    4    3
4    1    2    0    5    3    4
4    1    3    2    0    5    4
4    3    1    2    0    5    4
4    3    5    0    2    1    4
4    5    0    2    1    3    4
4    5    0    2    3    1    4
5    0    2    1    3    4    5
5    0    2    1    4    3    5
5    0    2    3    1    4    5
5    3    4    1    2    0    5
5    4    1    3    2    0    5
5    4    3    1    2    0    5``````
``````/*
Kotlin Program for
Print all Hamiltonian path present in a graph
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
fun printSolution(solution: Array < Int > , size: Int): Unit
{
var i: Int = 0;
while (i < size)
{
print("   " + solution[i]);
i += 1;
}
print("\n");
}
// Detect  hamiltonian path exists in this graph or not
fun findSolution(graph: Array < Array < Int >> , visited: Array < Boolean > , result: Array < Int > , node: Int, counter: Int, n: Int, start: Int): Unit
{
if (counter == n && node == start)
{
result[counter] = node;
this.printSolution(result, n + 1);
}
if (visited[node] == true)
{
return;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
var i: Int = 0;
while (i < n)
{
if (graph[node][i] == 1)
{
this.findSolution(graph, visited, result, i, counter + 1, n, start);
}
i += 1;
}
// reset the status of visiting node
visited[node] = false;
}
fun setDefault(visited: Array < Boolean > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
visited[i] = false;
i += 1;
}
}
// Handles the request of find and display hamiltonian path
fun hamiltonianCycle(graph: Array < Array < Int >> , n: Int): Unit
{
// Indicator of visited node
var visited: Array < Boolean > = Array(n)
{
false
};
// Used to store path information
var result: Array < Int > = Array(n + 1)
{
0
};
print("\n   Hamiltonian Cycle \n");
var i: Int = 0;
while (i < n)
{
this.setDefault(visited, n);
this.findSolution(graph, visited, result, i, 0, n, i);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
/*
0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1 ‒‒│‒‒‒‒‒‒‒│‒‒4
│ ╲ │       │ ╱
│  ╲│       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
var graph: Array < Array < Int >> = arrayOf(
arrayOf(0, 0, 1, 0, 0, 1),
arrayOf(0, 0, 1, 1, 1, 0),
arrayOf(1, 1, 0, 1, 0, 0),
arrayOf(0, 1, 1, 0, 1, 1),
arrayOf(0, 1, 0, 1, 0, 1),
arrayOf(1, 0, 0, 1, 1, 0)
);
// Number of graph node
var n: Int = graph.count();
}``````

Output

``````   Hamiltonian Cycle
0   2   1   3   4   5   0
0   2   1   4   3   5   0
0   2   3   1   4   5   0
0   5   3   4   1   2   0
0   5   4   1   3   2   0
0   5   4   3   1   2   0
1   2   0   5   3   4   1
1   2   0   5   4   3   1
1   3   2   0   5   4   1
1   3   4   5   0   2   1
1   4   3   5   0   2   1
1   4   5   0   2   3   1
2   0   5   3   4   1   2
2   0   5   4   1   3   2
2   0   5   4   3   1   2
2   1   3   4   5   0   2
2   1   4   3   5   0   2
2   3   1   4   5   0   2
3   1   2   0   5   4   3
3   1   4   5   0   2   3
3   2   0   5   4   1   3
3   4   1   2   0   5   3
3   4   5   0   2   1   3
3   5   0   2   1   4   3
4   1   2   0   5   3   4
4   1   3   2   0   5   4
4   3   1   2   0   5   4
4   3   5   0   2   1   4
4   5   0   2   1   3   4
4   5   0   2   3   1   4
5   0   2   1   3   4   5
5   0   2   1   4   3   5
5   0   2   3   1   4   5
5   3   4   1   2   0   5
5   4   1   3   2   0   5
5   4   3   1   2   0   5``````

Result Explanation

The output represents all the Hamiltonian paths present in the given graph. Each line of the output corresponds to a different path. For example, the first line "0 2 1 3 4 5 0" represents a Hamiltonian path that starts at vertex 0, visits vertices 2, 1, 3, 4, and 5 in that order, and finally returns to vertex 0.

The algorithm works by systematically exploring all possible paths in the graph using backtracking. It starts from each vertex in the graph and recursively explores all adjacent vertices, marking them as visited. If a path of length V (number of vertices) is found, and the current vertex is the starting vertex, it means a Hamiltonian path has been found. The path is then printed.

The algorithm uses a visited array to keep track of the visited vertices and a result array to store the current path being explored. The setDefault function initializes the visited array at the beginning of each iteration. The hamiltonianCycle function initiates the exploration process by starting from each vertex in the graph and calling the findSolution function.

The time complexity of this algorithm is exponential, as it explores all possible paths in the graph. In the worst case, the number of paths to explore can be O(n!), where n is the number of vertices. This is because for each vertex, there can be (n-1)! possible permutations of the remaining vertices in a Hamiltonian path. Therefore, the algorithm's time complexity is O(n! * n^2), where n^2 accounts for the nested loop in the findSolution function.

The provided code and algorithm successfully print all Hamiltonian paths in a given graph. The algorithm explores all possible paths using backtracking and systematically generates the output. However, it's important to note that the algorithm's time complexity grows exponentially with the number of vertices, making it inefficient for large graphs.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.