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)
{
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 0
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