Print all Hamiltonian path present in a graph
The Hamiltonian path problem is a well-known problem in graph theory. It deals with finding a path in a graph that visits every vertex exactly once. In this article, we will discuss how to print all Hamiltonian paths present in a graph using a simple algorithm.
Problem Statement
Given a graph with V vertices, we want to find and print all the Hamiltonian paths present in the graph. A Hamiltonian path is a path that visits every vertex exactly once and returns to the starting vertex.
Let's consider an example graph:
0‒‒‒‒‒‒ 5
│ │╲
│ │ ╲
1‒‒‒│‒‒‒‒‒‒‒│‒‒4
│╲ │ │ ╱
│ ╲ │ │╱
│ 2‒‒‒‒‒‒‒3
│ │
└‒‒‒‒‒‒‒‒‒‒‒┘
----------------
graph
----------------
In the above graph, we can see that there are multiple Hamiltonian paths possible. Our goal is to find and print all these paths.
Pseudocode Algorithm
To solve this problem, we will use a backtracking algorithm that explores all possible paths in the graph. Here is the pseudocode for the algorithm:
function printSolution(solution[], size):
for i from 0 to size:
print solution[i]
function findSolution(graph[][], visited[], result[], node, start, counter):
if counter = V and node = start:
result[counter] = node
printSolution(result, V+1)
if counter >= V or visited[node] ≠ -1:
return
visited[node] = 1
result[counter] = node
for i from 0 to V:
if graph[node][i] = 1:
findSolution(graph, visited, result, i, start, counter+1)
visited[node] = -1
function setDefault(visited[]):
for i from 0 to V:
visited[i] = -1
function hamiltonianCycle(graph[][]):
visited[V]
result[V+1]
for i from 0 to V:
setDefault(visited)
findSolution(graph, visited, result, i, i, 0)
The printSolution function is responsible for printing the Hamiltonian path. The findSolution function recursively explores all possible paths in the graph, while keeping track of visited nodes and storing the current path in the result array. The setDefault function initializes the visited array, and the hamiltonianCycle function handles the request of finding all Hamiltonian paths in the graph.
Program Solution
// 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 5Result Explanation
The output represents all the Hamiltonian paths present in the given graph. Each line of the output corresponds to a different path. For example, the first line "0 2 1 3 4 5 0" represents a Hamiltonian path that starts at vertex 0, visits vertices 2, 1, 3, 4, and 5 in that order, and finally returns to vertex 0.
The algorithm works by systematically exploring all possible paths in the graph using backtracking. It starts from each vertex in the graph and recursively explores all adjacent vertices, marking them as visited. If a path of length V (number of vertices) is found, and the current vertex is the starting vertex, it means a Hamiltonian path has been found. The path is then printed.
The algorithm uses a visited array to keep track of the visited vertices and a result array to store the current path being explored. The setDefault function initializes the visited array at the beginning of each iteration. The hamiltonianCycle function initiates the exploration process by starting from each vertex in the graph and calling the findSolution function.
The time complexity of this algorithm is exponential, as it explores all possible paths in the graph. In the worst case, the number of paths to explore can be O(n!), where n is the number of vertices. This is because for each vertex, there can be (n-1)! possible permutations of the remaining vertices in a Hamiltonian path. Therefore, the algorithm's time complexity is O(n! * n^2), where n^2 accounts for the nested loop in the findSolution function.
The provided code and algorithm successfully print all Hamiltonian paths in a given graph. The algorithm explores all possible paths using backtracking and systematically generates the output. However, it's important to note that the algorithm's time complexity grows exponentially with the number of vertices, making it inefficient for large graphs.
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