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]
for each adjacent_node in graph[node]:
if graph[node][adjacent_node] is 1:
recursively call findSolution for adjacent_node
if Hamiltonian Cycle found:
return
visited[node] = -1Algorithm Explanation
- Initialize arrays
visitedandresultto keep track of visited vertices and store the Hamiltonian Cycle. - Start DFS from vertex
0and call thefindSolutionfunction. - Inside the
findSolutionfunction: a. Check if we have visited all vertices and returned to the starting vertex. If yes, store the path inresultand return. b. Check if the current node is already visited. If yes, return. c. Mark the current node as visited and store it in theresultarray. d. Iterate through adjacent vertices of the current node:- Recursively call
findSolutionfor unvisited adjacent vertices. - If Hamiltonian Cycle is found, return. e. Backtrack by resetting the status of the current node.
- Recursively call
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)
{
GraphCycle task = new GraphCycle();
/*
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;
task.hamiltonianCycle(graph,n);
}
}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()
{
GraphCycle task = GraphCycle();
/*
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 }
} ;
task.hamiltonianCycle(graph, V);
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)
{
GraphCycle task = new GraphCycle();
/*
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);
task.hamiltonianCycle(graph, n);
}
}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()
{
$task = new GraphCycle();
/*
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);
$task->hamiltonianCycle($graph, $n);
}
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()
{
var task = new GraphCycle();
/*
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;
task.hamiltonianCycle(graph, n);
}
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() :
task = GraphCycle()
#
# 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)
task.hamiltonianCycle(graph, n)
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()
task = GraphCycle.new()
#
# 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
task.hamiltonianCycle(graph, n)
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;
task.hamiltonianCycle(graph, n);
}
}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()
{
let task: GraphCycle = GraphCycle();
/*
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;
task.hamiltonianCycle(graph, n);
}
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
{
var task: GraphCycle = GraphCycle();
/*
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();
task.hamiltonianCycle(graph, n);
}Output
Hamiltonian Cycle
0 2 3 1 4 5 0Time 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.
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.
New Comment