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)
{
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 , 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;
task.hamiltonianCycle(graph, n);
}
}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()
{
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, 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}
};
task.hamiltonianCycle(graph, V);
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)
{
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 , 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);
task.hamiltonianCycle(graph, n);
}
}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()
{
$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, 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);
$task->hamiltonianCycle($graph, $n);
}
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()
{
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, 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;
task.hamiltonianCycle(graph, n);
}
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() :
task = GraphCycle()
#
# 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)
task.hamiltonianCycle(graph, n)
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()
task = GraphCycle.new()
#
# 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
task.hamiltonianCycle(graph, n)
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;
task.hamiltonianCycle(graph, n);
}
}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()
{
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, 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;
task.hamiltonianCycle(graph, n);
}
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
{
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, 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();
task.hamiltonianCycle(graph, n);
}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
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