Skip to main content

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




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