Skip to main content

Hamiltonian Cycle

Here given code implementation process.

// 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
Last updated on by Kalkicode




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