Hamiltonian Cycle

Here given code implementation process.

``````// C Program
// Hamiltonian Cycle
#include <stdio.h>

#define V 6
// Print the solution of Hamiltonian Cycle
void printSolution(int solution[], int size)
{
printf("\n  Hamiltonian Cycle \n");
for (int i = 0; i < size; ++i)
{
printf("  %d", solution[i]);
}
}
// Detect  hamiltonian path exists in this graph or not
int findSolution(int graph[V][V], int visited[], int result[], int node, int counter)
{
if (counter == V)
{
if (node == 0)
{
result[counter] = node;
// This we get solution
// Stop process
return 1;
}
return 0;
}
if (visited[node] != -1)
{
return 0;
}
// indicates visiting node
visited[node] = 1;
// Store path result
result[counter] = node;
for (int i = 0; i < V; ++i)
{
if (graph[node][i] == 1)
{
if (findSolution(graph, visited, result, i, counter + 1) == 1)
{
// When Hamiltonian Cycle exist
return 1;
}
}
}
// reset the status of visiting node
visited[node] = -1;
return 0;
}
// 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];
for (int i = 0; i < V; ++i)
{
visited[i] = -1;
}
if (findSolution(graph, visited, result, 0, 0) == 1)
{
// Display hamiltonian Cycle
printSolution(result, V + 1);
}
else
{
printf("\n Hamiltonian Cycle not exists \n");
}
}
int main(int argc, char
const *argv[])
{
/*

0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1‒‒‒│‒‒‒‒‒‒‒│‒‒4
│   │       │ ╱
│   │       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
*/
// Adjacency matrix of a graph
int graph[V][V] = {
{ 0 , 0 , 1 , 0 , 0 , 1 } ,
{ 0 , 0 , 0 , 1 , 1 , 0 } ,
{ 1 , 0 , 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  3  1  4  5  0``````
``````/*
Java Program for
Hamiltonian Cycle
*/

class GraphCycle
{
// Print the solution of Hamiltonian Cycle
public void printSolution(int[] solution, int size)
{
System.out.print("\n Hamiltonian Cycle \n");
for (int i = 0; i < size; ++i)
{
System.out.print("  " + solution[i] );
}
}
// Detect  hamiltonian path exists in this graph or not
public boolean findSolution(int[][] graph, boolean[] visited, int[] result, int node, int counter, int n)
{
if (counter == n)
{
if (node == 0)
{
result[counter] = node;
// This we get solution
// Stop process
return true;
}
return false;
}
if (visited[node] == true)
{
return false;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (int i = 0; i < n; ++i)
{
if (graph[node][i] == 1)
{
if (findSolution(graph, visited, result, i, counter + 1,n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
}
// reset the status of visiting node
visited[node] = false;
return false;
}
// Handles the request of finding 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];
for (int i = 0; i < n; ++i)
{
visited[i] = false;
}
if (findSolution(graph, visited, result, 0, 0,n) == true)
{
// Display hamiltonian Cycle
printSolution(result, n + 1);
}
else
{
System.out.print("\n Hamiltonian Cycle not exists \n");
}
}
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 , 0 , 1 , 1 , 0 } ,
{ 1 , 0 , 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  3  1  4  5  0``````
``````// Include header file
#include <iostream>

#define V 6
using namespace std;
/*
C++ Program for
Hamiltonian Cycle
*/
class GraphCycle
{
public:
// Print the solution of Hamiltonian Cycle
void printSolution(int solution[], int size)
{
cout << "\n Hamiltonian Cycle \n";
for (int i = 0; i < size; ++i)
{
cout << "  " << solution[i];
}
}
// Detect  hamiltonian path exists in this graph or not
bool findSolution(int graph[V][V], bool visited[], int result[], int node, int counter, int n)
{
if (counter == n)
{
if (node == 0)
{
// This we get solution
// Stop process
result[counter] = node;
return true;
}
return false;
}
if (visited[node] == true)
{
return false;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (int i = 0; i < n; ++i)
{
if (graph[node][i] == 1)
{
if (this->findSolution(graph, visited, result, i, counter + 1, n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
}
// reset the status of visiting node
visited[node] = false;
return false;
}
// Handles the request of finding 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];
for (int i = 0; i < n; ++i)
{
visited[i] = false;
}
if (this->findSolution(graph, visited, result, 0, 0, n) == true)
{
// Display hamiltonian Cycle
this->printSolution(result, n + 1);
}
else
{
cout << "\n Hamiltonian Cycle not exists \n";
}
}
};
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 , 0 , 1 , 1 , 0 } ,
{ 1 , 0 , 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  3  1  4  5  0``````
``````// Include namespace system
using System;
/*
C# Program for
Hamiltonian Cycle
*/
public class GraphCycle
{
// Print the solution of Hamiltonian Cycle
public void printSolution(int[] solution, int size)
{
Console.Write("\n Hamiltonian Cycle \n");
for (int i = 0; i < size; ++i)
{
Console.Write("  " + solution[i]);
}
}
// Detect  hamiltonian path exists in this graph or not
public Boolean findSolution(int[,] graph, Boolean[] visited, int[] result, int node, int counter, int n)
{
if (counter == n)
{
if (node == 0)
{
// This we get solution
// Stop process
result[counter] = node;
return true;
}
return false;
}
if (visited[node] == true)
{
return false;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (int i = 0; i < n; ++i)
{
if (graph[node,i] == 1)
{
if (findSolution(graph, visited, result, i, counter + 1, n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
}
// reset the status of visiting node
visited[node] = false;
return false;
}
// Handles the request of finding 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];
for (int i = 0; i < n; ++i)
{
visited[i] = false;
}
if (findSolution(graph, visited, result, 0, 0, n) == true)
{
// Display hamiltonian Cycle
printSolution(result, n + 1);
}
else
{
Console.Write("\n Hamiltonian Cycle not exists \n");
}
}
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 , 0 , 1 , 1 , 0 } ,
{ 1 , 0 , 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  3  1  4  5  0``````
``````<?php
/*
Php Program for
Hamiltonian Cycle
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
public  function printSolution( & \$solution, \$size)
{
echo "\n Hamiltonian Cycle \n";
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$solution[\$i];
}
}
// Detect  hamiltonian path exists in this graph or not
public  function findSolution( & \$graph, & \$visited, & \$result, \$node, \$counter, \$n)
{
if (\$counter == \$n)
{
if (\$node == 0)
{
// This we get solution
// Stop process
\$result[\$counter] = \$node;
return true;
}
return false;
}
if (\$visited[\$node] == true)
{
return false;
}
// indicates visiting node
\$visited[\$node] = true;
// Store path result
\$result[\$counter] = \$node;
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$graph[\$node][\$i] == 1)
{
if (\$this->findSolution(\$graph, \$visited, \$result, \$i, \$counter + 1, \$n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
}
// reset the status of visiting node
\$visited[\$node] = false;
return false;
}
// Handles the request of finding 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);
if (\$this->findSolution(\$graph, \$visited, \$result, 0, 0, \$n) == true)
{
// Display hamiltonian Cycle
\$this->printSolution(\$result, \$n + 1);
}
else
{
echo "\n Hamiltonian Cycle not exists \n";
}
}
}

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, 0, 1, 1, 0),
array(1, 0, 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  3  1  4  5  0``````
``````/*
Node Js Program for
Hamiltonian Cycle
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
printSolution(solution, size)
{
process.stdout.write("\n Hamiltonian Cycle \n");
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + solution[i]);
}
}
// Detect  hamiltonian path exists in this graph or not
findSolution(graph, visited, result, node, counter, n)
{
if (counter == n)
{
if (node == 0)
{
// This we get solution
// Stop process
result[counter] = node;
return true;
}
return false;
}
if (visited[node] == true)
{
return false;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
for (var i = 0; i < n; ++i)
{
if (graph[node][i] == 1)
{
if (this.findSolution(graph, visited, result, i, counter + 1, n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
}
// reset the status of visiting node
visited[node] = false;
return false;
}
// Handles the request of finding 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);
if (this.findSolution(graph, visited, result, 0, 0, n) == true)
{
// Display hamiltonian Cycle
this.printSolution(result, n + 1);
}
else
{
process.stdout.write("\n Hamiltonian Cycle not exists \n");
}
}
}

function main()
{
/*
0‒‒‒‒‒‒ 5
│       │╲
│       │ ╲
1‒‒‒│‒‒‒‒‒‒‒│‒‒4
│   │       │ ╱
│   │       │╱
│   2‒‒‒‒‒‒‒3
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------

*/
// Adjacency matrix of a graph
var graph = [
[0, 0, 1, 0, 0, 1] ,
[0, 0, 0, 1, 1, 0] ,
[1, 0, 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  3  1  4  5  0``````
``````#   Python 3 Program for
#   Hamiltonian Cycle

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

#  Detect  hamiltonian path exists in this graph or not
def findSolution(self, graph, visited, result, node, counter, n) :
if (counter == n) :
if (node == 0) :
#  This we get solution
#  Stop process
result[counter] = node
return True

return False

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

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

i += 1

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

#  Handles the request of finding hamiltonian path
def hamiltonianCycle(self, graph, n) :
#  Indicator of visited node
visited = [False] * (n)
#  Used to store path information
result = [0] * (n + 1)
if (self.findSolution(graph, visited, result, 0, 0, n) == True) :
#  Display hamiltonian Cycle
self.printSolution(result, n + 1)
else :
print("\n Hamiltonian Cycle not exists ")

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

#  Adjacency matrix of a graph
graph = [
[0, 0, 1, 0, 0, 1] ,
[0, 0, 0, 1, 1, 0] ,
[1, 0, 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   3   1   4   5   0``````
``````#   Ruby Program for
#   Hamiltonian Cycle

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

end

#  Detect  hamiltonian path exists in this graph or not
def findSolution(graph, visited, result, node, counter, n)
if (counter == n)
if (node == 0)
#  This we get solution
#  Stop process
result[counter] = node
return true
end

return false
end

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

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

end

i += 1
end

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

#  Handles the request of finding 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}
if (self.findSolution(graph, visited, result, 0, 0, n) == true)
#  Display hamiltonian Cycle
self.printSolution(result, n + 1)
else
print("\n Hamiltonian Cycle not exists \n")
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, 0, 1, 1, 0] ,
[1, 0, 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  3  1  4  5  0``````
``````/*
Scala Program for
Hamiltonian Cycle
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
def printSolution(solution: Array[Int], size: Int): Unit = {
print("\n Hamiltonian Cycle \n");
var i: Int = 0;
while (i < size)
{
print("  " + solution(i));
i += 1;
}
}
// 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): Boolean = {
if (counter == n)
{
if (node == 0)
{
// This we get solution
// Stop process
result(counter) = node;
return true;
}
return false;
}
if (visited(node) == true)
{
return false;
}
// indicates visiting node
visited(node) = true;
// Store path result
result(counter) = node;
var i: Int = 0;
while (i < n)
{
if (graph(node)(i) == 1)
{
if (this.findSolution(graph, visited, result, i, counter + 1, n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
i += 1;
}
// reset the status of visiting node
visited(node) = false;
return false;
}
// Handles the request of finding 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);
if (this.findSolution(graph, visited, result, 0, 0, n) == true)
{
// Display hamiltonian Cycle
this.printSolution(result, n + 1);
}
else
{
print("\n Hamiltonian Cycle not exists \n");
}
}
}
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, 0, 1, 1, 0),
Array(1, 0, 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  3  1  4  5  0``````
``````/*
Swift 4 Program for
Hamiltonian Cycle
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
func printSolution(_ solution: [Int], _ size: Int)
{
print("\n Hamiltonian Cycle ");
var i: Int = 0;
while (i < size)
{
print("  ", solution[i], terminator: "");
i += 1;
}
}
// 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)->Bool
{
if (counter == n)
{
if (node == 0)
{
// This we get solution
// Stop process
result[counter] = node;
return true;
}
return false;
}
if (visited[node] == true)
{
return false;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
var i: Int = 0;
while (i < n)
{
if (graph[node][i] == 1)
{
if (self.findSolution(graph, &visited, &result, i, counter + 1, n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
i += 1;
}
// reset the status of visiting node
visited[node] = false;
return false;
}
// Handles the request of finding 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);
if (self.findSolution(graph, &visited, &result, 0, 0, n) == true)
{
// Display hamiltonian Cycle
self.printSolution(result, n + 1);
}
else
{
print("\n Hamiltonian Cycle not exists ");
}
}
}
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, 0, 1, 1, 0] , [1, 0, 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   3   1   4   5   0``````
``````/*
Kotlin Program for
Hamiltonian Cycle
*/
class GraphCycle
{
// Print the solution of Hamiltonian Cycle
fun printSolution(solution: Array < Int > , size: Int): Unit
{
print("\n Hamiltonian Cycle \n");
var i: Int = 0;
while (i < size)
{
print("  " + solution[i]);
i += 1;
}
}
// 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): Boolean
{
if (counter == n)
{
if (node == 0)
{
// This we get solution
// Stop process
result[counter] = node;
return true;
}
return false;
}
if (visited[node] == true)
{
return false;
}
// indicates visiting node
visited[node] = true;
// Store path result
result[counter] = node;
var i: Int = 0;
while (i < n)
{
if (graph[node][i] == 1)
{
if (this.findSolution(graph, visited, result, i, counter + 1, n) == true)
{
// When Hamiltonian Cycle exist
return true;
}
}
i += 1;
}
// reset the status of visiting node
visited[node] = false;
return false;
}
// Handles the request of finding 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
};
if (this.findSolution(graph, visited, result, 0, 0, n) == true)
{
// Display hamiltonian Cycle
this.printSolution(result, n + 1);
}
else
{
print("\n Hamiltonian Cycle not exists \n");
}
}
}
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, 0, 1, 1, 0),
arrayOf(1, 0, 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  3  1  4  5  0``````

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.