Posted on by Kalkicode
Code Graph

Hamiltonian Cycle

A Hamiltonian cycle is a fundamental concept in graph theory, representing a cycle in a graph that visits each vertex exactly once and returns to the starting vertex. This article delves into the Hamiltonian Cycle problem, providing a detailed explanation of the algorithm, accompanied by a C code implementation and its corresponding output.

Problem Statement

Given a graph, the Hamiltonian Cycle problem aims to determine if there exists a cycle that visits every vertex exactly once and returns to the starting vertex.

Description with Example

Imagine a scenario where we have a graph that represents a network of cities, and the edges between cities represent connections or roads. The Hamiltonian Cycle problem is akin to finding a circular route that passes through each city without repeating any and eventually brings us back to the starting city.


    0‒‒‒‒‒‒ 5
    │       │╲
    │       │ ╲
1‒‒‒│‒‒‒‒‒‒‒│‒‒4
│   │       │ ╱
│   │       │╱
│   2‒‒‒‒‒‒‒3    
│           │
└‒‒‒‒‒‒‒‒‒‒‒┘   
----------------
    graph
----------------
Hamiltonian Cycle
0  2  3  1  4  5  0

Note : more than one hamiltonian Cycle possible in graph.

Idea to Solve

The Hamiltonian Cycle problem is typically solved using a backtracking approach. We explore different paths in the graph while maintaining a record of visited vertices. If a path is found that satisfies the Hamiltonian Cycle criteria, we return it; otherwise, we backtrack and explore other paths.

Pseudocode

function findSolution(graph, visited, result, node, counter):
    if counter is equal to V:
        if node is equal to 0:
            store result and return
        return
    if visited[node] is not -1:
        return
    visited[node] = 1
    store node in result[counter]
    for each adjacent_node in graph[node]:
        if graph[node][adjacent_node] is 1:
            recursively call findSolution for adjacent_node
            if Hamiltonian Cycle found:
                return
    visited[node] = -1

Algorithm Explanation

  1. Initialize arrays visited and result to keep track of visited vertices and store the Hamiltonian Cycle.
  2. Start DFS from vertex 0 and call the findSolution function.
  3. Inside the findSolution function: a. Check if we have visited all vertices and returned to the starting vertex. If yes, store the path in result and return. b. Check if the current node is already visited. If yes, return. c. Mark the current node as visited and store it in the result array. d. Iterate through adjacent vertices of the current node:
    • Recursively call findSolution for unvisited adjacent vertices.
    • If Hamiltonian Cycle is found, return. e. Backtrack by resetting the status of the current node.

Code Solution

// C Program 
// Hamiltonian Cycle
#include <stdio.h>

#define V 6
// Print the solution of Hamiltonian Cycle
void printSolution(int solution[], int size)
{
    printf("\n  Hamiltonian Cycle \n");
    for (int i = 0; i < size; ++i)
    {
        printf("  %d", solution[i]);
    }
}
// Detect  hamiltonian path exists in this graph or not
int findSolution(int graph[V][V], int visited[], int result[], int node, int counter)
{
    if (counter == V)
    {
        if (node == 0)
        {
            result[counter] = node;
            // This we get solution
            // Stop process
            return 1;
        }
        return 0;
    }
    if (visited[node] != -1)
    {
        return 0;
    }
    // indicates visiting node 
    visited[node] = 1;
    // Store path result
    result[counter] = node;
    for (int i = 0; i < V; ++i)
    {
        if (graph[node][i] == 1)
        {
            if (findSolution(graph, visited, result, i, counter + 1) == 1)
            {
                // When Hamiltonian Cycle exist
                return 1;
            }
        }
    }
    // reset the status of visiting node
    visited[node] = -1;
    return 0;
}
// Handles the request of finding hamiltonian path
void hamiltonianCycle(int graph[V][V])
{
    // Indicator of visited node 
    int visited[V];
    // Used to store path information
    int result[V + 1];
    for (int i = 0; i < V; ++i)
    {
        visited[i] = -1;
    }
    if (findSolution(graph, visited, result, 0, 0) == 1)
    {
        // Display hamiltonian Cycle
        printSolution(result, V + 1);
    }
    else
    {
        printf("\n Hamiltonian Cycle not exists \n");
    }
}
int main(int argc, char
    const *argv[])
{
    /*

            0‒‒‒‒‒‒ 5
            │       │╲
            │       │ ╲
        1‒‒‒│‒‒‒‒‒‒‒│‒‒4
        │   │       │ ╱
        │   │       │╱
        │   2‒‒‒‒‒‒‒3    
        │           │
        └‒‒‒‒‒‒‒‒‒‒‒┘   
        ----------------
            graph
        ----------------
    */
    // Adjacency matrix of a graph
    int graph[V][V] = {
        { 0 , 0 , 1 , 0 , 0 , 1 } , 
        { 0 , 0 , 0 , 1 , 1 , 0 } , 
        { 1 , 0 , 0 , 1 , 0 , 0 } , 
        { 0 , 1 , 1 , 0 , 1 , 1 } , 
        { 0 , 1 , 0 , 1 , 0 , 1 } ,
        { 1 , 0 , 0 , 1 , 1 , 0 }
    };
    hamiltonianCycle(graph);
    return 0;
}

Output

  Hamiltonian Cycle
  0  2  3  1  4  5  0
/* 
  Java Program for
  Hamiltonian Cycle
*/

class GraphCycle
{
    // Print the solution of Hamiltonian Cycle
    public void printSolution(int[] solution, int size)
    {
        System.out.print("\n Hamiltonian Cycle \n");
        for (int i = 0; i < size; ++i)
        {
            System.out.print("  " + solution[i] );
        }
    }
    // Detect  hamiltonian path exists in this graph or not
    public boolean findSolution(int[][] graph, boolean[] visited, int[] result, int node, int counter, int n)
    {
        if (counter == n)
        {
            if (node == 0)
            {
                result[counter] = node;
                // This we get solution
                // Stop process
                return true;
            }
            return false;
        }
        if (visited[node] == true)
        {
            return false;
        }
        // indicates visiting node 
        visited[node] = true;
        // Store path result
        result[counter] = node;
        for (int i = 0; i < n; ++i)
        {
            if (graph[node][i] == 1)
            {
                if (findSolution(graph, visited, result, i, counter + 1,n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
        }
        // reset the status of visiting node
        visited[node] = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    public void hamiltonianCycle(int[][] graph, int n)
    {
        // Indicator of visited node 
        boolean[] visited = new boolean[n];
        // Used to store path information
        int[] result = new int[n + 1];
        for (int i = 0; i < n; ++i)
        {
            visited[i] = false;
        }
        if (findSolution(graph, visited, result, 0, 0,n) == true)
        {
            // Display hamiltonian Cycle
            printSolution(result, n + 1);
        }
        else
        {
            System.out.print("\n Hamiltonian Cycle not exists \n");
        }
    }
    public static void main(String[] args)
    {

    GraphCycle task = new GraphCycle();        
    /*

            0‒‒‒‒‒‒ 5
            │       │╲
            │       │ ╲
        1‒‒‒│‒‒‒‒‒‒‒│‒‒4
        │   │       │ ╱
        │   │       │╱
        │   2‒‒‒‒‒‒‒3    
        │           │
        └‒‒‒‒‒‒‒‒‒‒‒┘   
        ----------------
            graph
        ----------------
    */
    // Adjacency matrix of a graph
    int[][] graph = 
    {
        { 0 , 0 , 1 , 0 , 0 , 1 } , 
        { 0 , 0 , 0 , 1 , 1 , 0 } , 
        { 1 , 0 , 0 , 1 , 0 , 0 } , 
        { 0 , 1 , 1 , 0 , 1 , 1 } , 
        { 0 , 1 , 0 , 1 , 0 , 1 } , 
        { 1 , 0 , 0 , 1 , 1 , 0 }
    };

    // Number of graph node
    int n = graph.length;

    task.hamiltonianCycle(graph,n);
    }
}

Output

 Hamiltonian Cycle
  0  2  3  1  4  5  0
// Include header file
#include <iostream>

#define V 6
using namespace std;
/*
  C++ Program for
  Hamiltonian Cycle
*/
class GraphCycle
{
    public:
        // Print the solution of Hamiltonian Cycle
        void printSolution(int solution[], int size)
        {
            cout << "\n Hamiltonian Cycle \n";
            for (int i = 0; i < size; ++i)
            {
                cout << "  " << solution[i];
            }
        }
    // Detect  hamiltonian path exists in this graph or not
    bool findSolution(int graph[V][V], bool visited[], int result[], int node, int counter, int n)
    {
        if (counter == n)
        {
            if (node == 0)
            {
                // This we get solution
                // Stop process
                result[counter] = node;
                return true;
            }
            return false;
        }
        if (visited[node] == true)
        {
            return false;
        }
        // indicates visiting node
        visited[node] = true;
        // Store path result
        result[counter] = node;
        for (int i = 0; i < n; ++i)
        {
            if (graph[node][i] == 1)
            {
                if (this->findSolution(graph, visited, result, i, counter + 1, n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
        }
        // reset the status of visiting node
        visited[node] = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    void hamiltonianCycle(int graph[V][V], int n)
    {
        // Indicator of visited node
        bool visited[n];
        // Used to store path information
        int result[n + 1];
        for (int i = 0; i < n; ++i)
        {
            visited[i] = false;
        }
        if (this->findSolution(graph, visited, result, 0, 0, n) == true)
        {
            // Display hamiltonian Cycle
            this->printSolution(result, n + 1);
        }
        else
        {
            cout << "\n Hamiltonian Cycle not exists \n";
        }
    }
};
int main()
{
    GraphCycle task = GraphCycle();
    /*
                0‒‒‒‒‒‒ 5
                │       │╲
                │       │ ╲
            1‒‒‒│‒‒‒‒‒‒‒│‒‒4
            │   │       │ ╱
            │   │       │╱
            │   2‒‒‒‒‒‒‒3    
            │           │
            └‒‒‒‒‒‒‒‒‒‒‒┘   
            ----------------
                graph
            ----------------
        
    */
    // Adjacency matrix of a graph
    int graph[V][V] = {
       { 0 , 0 , 1 , 0 , 0 , 1 } ,
       { 0 , 0 , 0 , 1 , 1 , 0 } ,
       { 1 , 0 , 0 , 1 , 0 , 0 } ,
       { 0 , 1 , 1 , 0 , 1 , 1 } ,
       { 0 , 1 , 0 , 1 , 0 , 1 } ,
       { 1 , 0 , 0 , 1 , 1 , 0 }
     } ;
    task.hamiltonianCycle(graph, V);
    return 0;
}

Output

 Hamiltonian Cycle
  0  2  3  1  4  5  0
// Include namespace system
using System;
/* 
  C# Program for
  Hamiltonian Cycle
*/
public class GraphCycle
{
    // Print the solution of Hamiltonian Cycle
    public void printSolution(int[] solution, int size)
    {
        Console.Write("\n Hamiltonian Cycle \n");
        for (int i = 0; i < size; ++i)
        {
            Console.Write("  " + solution[i]);
        }
    }
    // Detect  hamiltonian path exists in this graph or not
    public Boolean findSolution(int[,] graph, Boolean[] visited, int[] result, int node, int counter, int n)
    {
        if (counter == n)
        {
            if (node == 0)
            {
                // This we get solution
                // Stop process
                result[counter] = node;
                return true;
            }
            return false;
        }
        if (visited[node] == true)
        {
            return false;
        }
        // indicates visiting node
        visited[node] = true;
        // Store path result
        result[counter] = node;
        for (int i = 0; i < n; ++i)
        {
            if (graph[node,i] == 1)
            {
                if (findSolution(graph, visited, result, i, counter + 1, n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
        }
        // reset the status of visiting node
        visited[node] = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    public void hamiltonianCycle(int[,] graph, int n)
    {
        // Indicator of visited node
        Boolean[] visited = new Boolean[n];
        // Used to store path information
        int[] result = new int[n + 1];
        for (int i = 0; i < n; ++i)
        {
            visited[i] = false;
        }
        if (findSolution(graph, visited, result, 0, 0, n) == true)
        {
            // Display hamiltonian Cycle
            printSolution(result, n + 1);
        }
        else
        {
            Console.Write("\n Hamiltonian Cycle not exists \n");
        }
    }
    public static void Main(String[] args)
    {
        GraphCycle task = new GraphCycle();
        /*
                    0‒‒‒‒‒‒ 5
                    │       │╲
                    │       │ ╲
                1‒‒‒│‒‒‒‒‒‒‒│‒‒4
                │   │       │ ╱
                │   │       │╱
                │   2‒‒‒‒‒‒‒3    
                │           │
                └‒‒‒‒‒‒‒‒‒‒‒┘   
                ----------------
                    graph
                ----------------
            
        */
        // Adjacency matrix of a graph
        int[,] graph = {
            { 0 , 0 , 1 , 0 , 0 , 1 } , 
            { 0 , 0 , 0 , 1 , 1 , 0 } , 
            { 1 , 0 , 0 , 1 , 0 , 0 } , 
            { 0 , 1 , 1 , 0 , 1 , 1 } , 
            { 0 , 1 , 0 , 1 , 0 , 1 } ,
            { 1 , 0 , 0 , 1 , 1 , 0 }
        };
        // Number of graph node
        int n = graph.GetLength(0);
        task.hamiltonianCycle(graph, n);
    }
}

Output

 Hamiltonian Cycle
  0  2  3  1  4  5  0
<?php
/* 
  Php Program for
  Hamiltonian Cycle
*/
class GraphCycle
{
    // Print the solution of Hamiltonian Cycle
    public  function printSolution( & $solution, $size)
    {
        echo "\n Hamiltonian Cycle \n";
        for ($i = 0; $i < $size; ++$i)
        {
            echo "  ". $solution[$i];
        }
    }
    // Detect  hamiltonian path exists in this graph or not
    public  function findSolution( & $graph, & $visited, & $result, $node, $counter, $n)
    {
        if ($counter == $n)
        {
            if ($node == 0)
            {
                // This we get solution
                // Stop process
                $result[$counter] = $node;
                return true;
            }
            return false;
        }
        if ($visited[$node] == true)
        {
            return false;
        }
        // indicates visiting node
        $visited[$node] = true;
        // Store path result
        $result[$counter] = $node;
        for ($i = 0; $i < $n; ++$i)
        {
            if ($graph[$node][$i] == 1)
            {
                if ($this->findSolution($graph, $visited, $result, $i, $counter + 1, $n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
        }
        // reset the status of visiting node
        $visited[$node] = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    public  function hamiltonianCycle( & $graph, $n)
    {
        // Indicator of visited node
        $visited = array_fill(0, $n, false);
        // Used to store path information
        $result = array_fill(0, $n + 1, 0);
        if ($this->findSolution($graph, $visited, $result, 0, 0, $n) == true)
        {
            // Display hamiltonian Cycle
            $this->printSolution($result, $n + 1);
        }
        else
        {
            echo "\n Hamiltonian Cycle not exists \n";
        }
    }
}

function main()
{
    $task = new GraphCycle();
    /*
                0‒‒‒‒‒‒ 5
                │       │╲
                │       │ ╲
            1‒‒‒│‒‒‒‒‒‒‒│‒‒4
            │   │       │ ╱
            │   │       │╱
            │   2‒‒‒‒‒‒‒3    
            │           │
            └‒‒‒‒‒‒‒‒‒‒‒┘   
            ----------------
                graph
            ----------------
        
    */
    // Adjacency matrix of a graph
    $graph = array(
      array(0, 0, 1, 0, 0, 1), 
      array(0, 0, 0, 1, 1, 0), 
      array(1, 0, 0, 1, 0, 0), 
      array(0, 1, 1, 0, 1, 1), 
      array(0, 1, 0, 1, 0, 1), 
      array(1, 0, 0, 1, 1, 0)
    );
    // Number of graph node
    $n = count($graph);
    $task->hamiltonianCycle($graph, $n);
}
main();

Output

 Hamiltonian Cycle
  0  2  3  1  4  5  0
/* 
  Node Js Program for
  Hamiltonian Cycle
*/
class GraphCycle
{
    // Print the solution of Hamiltonian Cycle
    printSolution(solution, size)
    {
        process.stdout.write("\n Hamiltonian Cycle \n");
        for (var i = 0; i < size; ++i)
        {
            process.stdout.write("  " + solution[i]);
        }
    }
    // Detect  hamiltonian path exists in this graph or not
    findSolution(graph, visited, result, node, counter, n)
    {
        if (counter == n)
        {
            if (node == 0)
            {
                // This we get solution
                // Stop process
                result[counter] = node;
                return true;
            }
            return false;
        }
        if (visited[node] == true)
        {
            return false;
        }
        // indicates visiting node
        visited[node] = true;
        // Store path result
        result[counter] = node;
        for (var i = 0; i < n; ++i)
        {
            if (graph[node][i] == 1)
            {
                if (this.findSolution(graph, visited, result, i, counter + 1, n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
        }
        // reset the status of visiting node
        visited[node] = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    hamiltonianCycle(graph, n)
    {
        // Indicator of visited node
        var visited = Array(n).fill(false);
        // Used to store path information
        var result = Array(n + 1).fill(0);
        if (this.findSolution(graph, visited, result, 0, 0, n) == true)
        {
            // Display hamiltonian Cycle
            this.printSolution(result, n + 1);
        }
        else
        {
            process.stdout.write("\n Hamiltonian Cycle not exists \n");
        }
    }
}

function main()
{
    var task = new GraphCycle();
    /*
                0‒‒‒‒‒‒ 5
                │       │╲
                │       │ ╲
            1‒‒‒│‒‒‒‒‒‒‒│‒‒4
            │   │       │ ╱
            │   │       │╱
            │   2‒‒‒‒‒‒‒3    
            │           │
            └‒‒‒‒‒‒‒‒‒‒‒┘   
            ----------------
                graph
            ----------------
        
    */
    // Adjacency matrix of a graph
    var graph = [
      [0, 0, 1, 0, 0, 1] , 
      [0, 0, 0, 1, 1, 0] , 
      [1, 0, 0, 1, 0, 0] , 
      [0, 1, 1, 0, 1, 1] , 
      [0, 1, 0, 1, 0, 1] , 
      [1, 0, 0, 1, 1, 0]
    ];
    // Number of graph node
    var n = graph.length;
    task.hamiltonianCycle(graph, n);
}
main();

Output

 Hamiltonian Cycle
  0  2  3  1  4  5  0
#   Python 3 Program for
#   Hamiltonian Cycle

class GraphCycle :
    #  Print the solution of Hamiltonian Cycle
    def printSolution(self, solution, size) :
        print("\n Hamiltonian Cycle ")
        i = 0
        while (i < size) :
            print("  ", solution[i], end = "")
            i += 1
        
    
    #  Detect  hamiltonian path exists in this graph or not
    def findSolution(self, graph, visited, result, node, counter, n) :
        if (counter == n) :
            if (node == 0) :
                #  This we get solution
                #  Stop process
                result[counter] = node
                return True
            
            return False
        
        if (visited[node] == True) :
            return False
        
        #  indicates visiting node
        visited[node] = True
        #  Store path result
        result[counter] = node
        i = 0
        while (i < n) :
            if (graph[node][i] == 1) :
                if (self.findSolution(graph, visited, result, i, counter + 1, n) == True) :
                    #  When Hamiltonian Cycle exist
                    return True
                
            
            i += 1
        
        #  reset the status of visiting node
        visited[node] = False
        return False
    
    #  Handles the request of finding hamiltonian path
    def hamiltonianCycle(self, graph, n) :
        #  Indicator of visited node
        visited = [False] * (n)
        #  Used to store path information
        result = [0] * (n + 1)
        if (self.findSolution(graph, visited, result, 0, 0, n) == True) :
            #  Display hamiltonian Cycle
            self.printSolution(result, n + 1)
        else :
            print("\n Hamiltonian Cycle not exists ")
        
    

def main() :
    task = GraphCycle()
    # 
    #             0‒‒‒‒‒‒ 5
    #             │       │╲
    #             │       │ ╲
    #         1‒‒‒│‒‒‒‒‒‒‒│‒‒4
    #         │   │       │ ╱
    #         │   │       │╱
    #         │   2‒‒‒‒‒‒‒3    
    #         │           │
    #         └‒‒‒‒‒‒‒‒‒‒‒┘   
    #         ----------------
    #             graph
    #         ----------------
    #     
    
    #  Adjacency matrix of a graph
    graph = [
      [0, 0, 1, 0, 0, 1] , 
      [0, 0, 0, 1, 1, 0] , 
      [1, 0, 0, 1, 0, 0] , 
      [0, 1, 1, 0, 1, 1] , 
      [0, 1, 0, 1, 0, 1] , 
      [1, 0, 0, 1, 1, 0]
    ]
    #  Number of graph node
    n = len(graph)
    task.hamiltonianCycle(graph, n)

if __name__ == "__main__": main()

Output

 Hamiltonian Cycle
   0   2   3   1   4   5   0
#   Ruby Program for
#   Hamiltonian Cycle

class GraphCycle 
    #  Print the solution of Hamiltonian Cycle
    def printSolution(solution, size) 
        print("\n Hamiltonian Cycle \n")
        i = 0
        while (i < size) 
            print("  ", solution[i])
            i += 1
        end

    end

    #  Detect  hamiltonian path exists in this graph or not
    def findSolution(graph, visited, result, node, counter, n) 
        if (counter == n) 
            if (node == 0) 
                #  This we get solution
                #  Stop process
                result[counter] = node
                return true
            end

            return false
        end

        if (visited[node] == true) 
            return false
        end

        #  indicates visiting node
        visited[node] = true
        #  Store path result
        result[counter] = node
        i = 0
        while (i < n) 
            if (graph[node][i] == 1) 
                if (self.findSolution(graph, visited, result, i, counter + 1, n) == true) 
                    #  When Hamiltonian Cycle exist
                    return true
                end

            end

            i += 1
        end

        #  reset the status of visiting node
        visited[node] = false
        return false
    end

    #  Handles the request of finding hamiltonian path
    def hamiltonianCycle(graph, n) 
        #  Indicator of visited node
        visited = Array.new(n) {false}
        #  Used to store path information
        result = Array.new(n + 1) {0}
        if (self.findSolution(graph, visited, result, 0, 0, n) == true) 
            #  Display hamiltonian Cycle
            self.printSolution(result, n + 1)
        else 
            print("\n Hamiltonian Cycle not exists \n")
        end

    end

end

def main() 
    task = GraphCycle.new()
    # 
    #             0‒‒‒‒‒‒ 5
    #             │       │╲
    #             │       │ ╲
    #         1‒‒‒│‒‒‒‒‒‒‒│‒‒4
    #         │   │       │ ╱
    #         │   │       │╱
    #         │   2‒‒‒‒‒‒‒3    
    #         │           │
    #         └‒‒‒‒‒‒‒‒‒‒‒┘   
    #         ----------------
    #             graph
    #         ----------------
    #     
    
    #  Adjacency matrix of a graph
    graph = [
      [0, 0, 1, 0, 0, 1] , 
      [0, 0, 0, 1, 1, 0] , 
      [1, 0, 0, 1, 0, 0] , 
      [0, 1, 1, 0, 1, 1] , 
      [0, 1, 0, 1, 0, 1] , 
      [1, 0, 0, 1, 1, 0]
    ]
    #  Number of graph node
    n = graph.length
    task.hamiltonianCycle(graph, n)
end

main()

Output

 Hamiltonian Cycle 
  0  2  3  1  4  5  0
/* 
  Scala Program for
  Hamiltonian Cycle
*/
class GraphCycle
{
    // Print the solution of Hamiltonian Cycle
    def printSolution(solution: Array[Int], size: Int): Unit = {
        print("\n Hamiltonian Cycle \n");
        var i: Int = 0;
        while (i < size)
        {
            print("  " + solution(i));
            i += 1;
        }
    }
    // Detect  hamiltonian path exists in this graph or not
    def findSolution(graph: Array[Array[Int]], visited: Array[Boolean], result: Array[Int], node: Int, counter: Int, n: Int): Boolean = {
        if (counter == n)
        {
            if (node == 0)
            {
                // This we get solution
                // Stop process
                result(counter) = node;
                return true;
            }
            return false;
        }
        if (visited(node) == true)
        {
            return false;
        }
        // indicates visiting node
        visited(node) = true;
        // Store path result
        result(counter) = node;
        var i: Int = 0;
        while (i < n)
        {
            if (graph(node)(i) == 1)
            {
                if (this.findSolution(graph, visited, result, i, counter + 1, n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
            i += 1;
        }
        // reset the status of visiting node
        visited(node) = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    def hamiltonianCycle(graph: Array[Array[Int]], n: Int): Unit = {
        // Indicator of visited node
        var visited: Array[Boolean] = Array.fill[Boolean](n)(false);
        // Used to store path information
        var result: Array[Int] = Array.fill[Int](n + 1)(0);
        if (this.findSolution(graph, visited, result, 0, 0, n) == true)
        {
            // Display hamiltonian Cycle
            this.printSolution(result, n + 1);
        }
        else
        {
            print("\n Hamiltonian Cycle not exists \n");
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: GraphCycle = new GraphCycle();
        /*
                    0‒‒‒‒‒‒ 5
                    │       │╲
                    │       │ ╲
                1‒‒‒│‒‒‒‒‒‒‒│‒‒4
                │   │       │ ╱
                │   │       │╱
                │   2‒‒‒‒‒‒‒3    
                │           │
                └‒‒‒‒‒‒‒‒‒‒‒┘   
                ----------------
                    graph
                ----------------
            
        */
        // Adjacency matrix of a graph
        var graph: Array[Array[Int]] = Array(
          Array(0, 0, 1, 0, 0, 1), 
          Array(0, 0, 0, 1, 1, 0), 
          Array(1, 0, 0, 1, 0, 0), 
          Array(0, 1, 1, 0, 1, 1), 
          Array(0, 1, 0, 1, 0, 1), 
          Array(1, 0, 0, 1, 1, 0)
        );
        // Number of graph node
        var n: Int = graph.length;
        task.hamiltonianCycle(graph, n);
    }
}

Output

 Hamiltonian Cycle
  0  2  3  1  4  5  0
/* 
  Swift 4 Program for
  Hamiltonian Cycle
*/
class GraphCycle
{
    // Print the solution of Hamiltonian Cycle
    func printSolution(_ solution: [Int], _ size: Int)
    {
        print("\n Hamiltonian Cycle ");
        var i: Int = 0;
        while (i < size)
        {
            print("  ", solution[i], terminator: "");
            i += 1;
        }
    }
    // Detect  hamiltonian path exists in this graph or not
    func findSolution(_ graph: [
        [Int]
    ], _ visited: inout[Bool], _ result: inout[Int], _ node: Int, _ counter: Int, _ n: Int)->Bool
    {
        if (counter == n)
        {
            if (node == 0)
            {
                // This we get solution
                // Stop process
                result[counter] = node;
                return true;
            }
            return false;
        }
        if (visited[node] == true)
        {
            return false;
        }
        // indicates visiting node
        visited[node] = true;
        // Store path result
        result[counter] = node;
        var i: Int = 0;
        while (i < n)
        {
            if (graph[node][i] == 1)
            {
                if (self.findSolution(graph, &visited, &result, i, counter + 1, n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
            i += 1;
        }
        // reset the status of visiting node
        visited[node] = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    func hamiltonianCycle(_ graph: [
        [Int]
    ], _ n: Int)
    {
        // Indicator of visited node
        var visited: [Bool] = Array(repeating: false, count: n);
        // Used to store path information
        var result: [Int] = Array(repeating: 0, count: n + 1);
        if (self.findSolution(graph, &visited, &result, 0, 0, n) == true)
        {
            // Display hamiltonian Cycle
            self.printSolution(result, n + 1);
        }
        else
        {
            print("\n Hamiltonian Cycle not exists ");
        }
    }
}
func main()
{
    let task: GraphCycle = GraphCycle();
    /*
                0‒‒‒‒‒‒ 5
                │       │╲
                │       │ ╲
            1‒‒‒│‒‒‒‒‒‒‒│‒‒4
            │   │       │ ╱
            │   │       │╱
            │   2‒‒‒‒‒‒‒3    
            │           │
            └‒‒‒‒‒‒‒‒‒‒‒┘   
            ----------------
                graph
            ----------------
        
    */
    // Adjacency matrix of a graph
    let graph: [
        [Int]
    ] = [
        [0, 0, 1, 0, 0, 1] , [0, 0, 0, 1, 1, 0] , [1, 0, 0, 1, 0, 0] , [0, 1, 1, 0, 1, 1] , [0, 1, 0, 1, 0, 1] , [1, 0, 0, 1, 1, 0]
    ];
    // Number of graph node
    let n: Int = graph.count;
    task.hamiltonianCycle(graph, n);
}
main();

Output

 Hamiltonian Cycle
   0   2   3   1   4   5   0
/* 
  Kotlin Program for
  Hamiltonian Cycle
*/
class GraphCycle
{
    // Print the solution of Hamiltonian Cycle
    fun printSolution(solution: Array < Int > , size: Int): Unit
    {
        print("\n Hamiltonian Cycle \n");
        var i: Int = 0;
        while (i < size)
        {
            print("  " + solution[i]);
            i += 1;
        }
    }
    // Detect  hamiltonian path exists in this graph or not
    fun findSolution(graph: Array < Array < Int >> , visited: Array < Boolean > , result: Array < Int > , node: Int, counter: Int, n: Int): Boolean
    {
        if (counter == n)
        {
            if (node == 0)
            {
                // This we get solution
                // Stop process
                result[counter] = node;
                return true;
            }
            return false;
        }
        if (visited[node] == true)
        {
            return false;
        }
        // indicates visiting node
        visited[node] = true;
        // Store path result
        result[counter] = node;
        var i: Int = 0;
        while (i < n)
        {
            if (graph[node][i] == 1)
            {
                if (this.findSolution(graph, visited, result, i, counter + 1, n) == true)
                {
                    // When Hamiltonian Cycle exist
                    return true;
                }
            }
            i += 1;
        }
        // reset the status of visiting node
        visited[node] = false;
        return false;
    }
    // Handles the request of finding hamiltonian path
    fun hamiltonianCycle(graph: Array < Array < Int >> , n: Int): Unit
    {
        // Indicator of visited node
        var visited: Array < Boolean > = Array(n)
        {
            false
        };
        // Used to store path information
        var result: Array < Int > = Array(n + 1)
        {
            0
        };
        if (this.findSolution(graph, visited, result, 0, 0, n) == true)
        {
            // Display hamiltonian Cycle
            this.printSolution(result, n + 1);
        }
        else
        {
            print("\n Hamiltonian Cycle not exists \n");
        }
    }
}
fun main(args: Array < String > ): Unit
{
    var task: GraphCycle = GraphCycle();
    /*
                0‒‒‒‒‒‒ 5
                │       │╲
                │       │ ╲
            1‒‒‒│‒‒‒‒‒‒‒│‒‒4
            │   │       │ ╱
            │   │       │╱
            │   2‒‒‒‒‒‒‒3    
            │           │
            └‒‒‒‒‒‒‒‒‒‒‒┘   
            ----------------
                graph
            ----------------
        
    */
    // Adjacency matrix of a graph
    var graph: Array < Array < Int >> = arrayOf(
      arrayOf(0, 0, 1, 0, 0, 1), 
      arrayOf(0, 0, 0, 1, 1, 0), 
      arrayOf(1, 0, 0, 1, 0, 0), 
      arrayOf(0, 1, 1, 0, 1, 1), 
      arrayOf(0, 1, 0, 1, 0, 1),
      arrayOf(1, 0, 0, 1, 1, 0)
    );
    // Number of graph node
    var n: Int = graph.count();
    task.hamiltonianCycle(graph, n);
}

Output

 Hamiltonian Cycle
  0  2  3  1  4  5  0

Time Complexity

The time complexity of the Hamiltonian Cycle algorithm depends on the number of vertices V and the number of edges E in the graph. In the worst case, the algorithm explores all possible paths, resulting in a time complexity of O(V!). However, with optimizations, the algorithm's time complexity can be reduced.

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