Posted on by Kalkicode
Code Graph

# Hamiltonian Cycle

A Hamiltonian cycle is a fundamental concept in graph theory, representing a cycle in a graph that visits each vertex exactly once and returns to the starting vertex. This article delves into the Hamiltonian Cycle problem, providing a detailed explanation of the algorithm, accompanied by a C code implementation and its corresponding output.

## Problem Statement

Given a graph, the Hamiltonian Cycle problem aims to determine if there exists a cycle that visits every vertex exactly once and returns to the starting vertex.

## Description with Example

Imagine a scenario where we have a graph that represents a network of cities, and the edges between cities represent connections or roads. The Hamiltonian Cycle problem is akin to finding a circular route that passes through each city without repeating any and eventually brings us back to the starting city.

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

Note : more than one hamiltonian Cycle possible in graph.
``````

## Idea to Solve

The Hamiltonian Cycle problem is typically solved using a backtracking approach. We explore different paths in the graph while maintaining a record of visited vertices. If a path is found that satisfies the Hamiltonian Cycle criteria, we return it; otherwise, we backtrack and explore other paths.

## Pseudocode

``````function findSolution(graph, visited, result, node, counter):
if counter is equal to V:
if node is equal to 0:
store result and return
return
if visited[node] is not -1:
return
visited[node] = 1
store node in result[counter]
if Hamiltonian Cycle found:
return
visited[node] = -1``````

## Algorithm Explanation

1. Initialize arrays `visited` and `result` to keep track of visited vertices and store the Hamiltonian Cycle.
2. Start DFS from vertex `0` and call the `findSolution` function.
3. Inside the `findSolution` function: a. Check if we have visited all vertices and returned to the starting vertex. If yes, store the path in `result` and return. b. Check if the current node is already visited. If yes, return. c. Mark the current node as visited and store it in the `result` array. d. Iterate through adjacent vertices of the current node:
• Recursively call `findSolution` for unvisited adjacent vertices.
• If Hamiltonian Cycle is found, return. e. Backtrack by resetting the status of the current node.

## Code Solution

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

## Time Complexity

The time complexity of the Hamiltonian Cycle algorithm depends on the number of vertices `V` and the number of edges `E` in the graph. In the worst case, the algorithm explores all possible paths, resulting in a time complexity of O(V!). However, with optimizations, the algorithm's time complexity can be reduced.

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

Categories
Relative Post