# Print all Hamiltonian path present in a graph

Here given code implementation process.

``````// 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``````

## 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.