Skip to main content

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   5

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





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment