Hamiltonian Path Java

PROGRAM TO SOLVE HAMILTONIAN CYCLE PROBLEM



class HamiltonianCycle
{
    final int V = 5;
    int path[];
 
    /* A utility function to check if the vertex v can be
       added at index 'pos'in the Hamiltonian Cycle
       constructed so far (stored in 'path[]') */
    boolean isSafe(int v, int graph[][], int path[], int pos)
    {
        /* Check if this vertex is an adjacent vertex of
           the previously added vertex. */
        if (graph[path[pos - 1]][v] == 0)
            return false;
 
        /* Check if the vertex has already been included.
           This step can be optimized by creating an array
           of size V */
        for (int i = 0; i < pos; i++)
            if (path[i] == v)
                return false;
 
        return true;
    }
 
    /* A recursive utility function to solve hamiltonian
       cycle problem */
    boolean hamCycleUtil(int graph[][], int path[], int pos)
    {
        /* base case: If all vertices are included in
           Hamiltonian Cycle */
        if (pos == V)
        {
            // And if there is an edge from the last included
            // vertex to the first vertex
            if (graph[path[pos - 1]][path[0]] == 1)
                return true;
            else
                return false;
        }
 
        // Try different vertices as a next candidate in
        // Hamiltonian Cycle. We don't try for 0 as we
        // included 0 as starting point in hamCycle()
        for (int v = 1; v < V; v++)
        {
            /* Check if this vertex can be added to Hamiltonian
               Cycle */
            if (isSafe(v, graph, path, pos))
            {
                path[pos] = v;
 
                /* recur to construct rest of the path */
                if (hamCycleUtil(graph, path, pos + 1) == true)
                    return true;
 
                /* If adding vertex v doesn't lead to a solution,
                   then remove it */
                path[pos] = -1;
            }
        }
 
        /* If no vertex can be added to Hamiltonian Cycle
           constructed so far, then return false */
        return false;
    }
 
    /* This function solves the Hamiltonian Cycle problem using
       Backtracking. It mainly uses hamCycleUtil() to solve the
       problem. It returns false if there is no Hamiltonian Cycle
       possible, otherwise return true and prints the path.
       Please note that there may be more than one solutions,
       this function prints one of the feasible solutions. */
    int hamCycle(int graph[][])
    {
        path = new int[V];
        for (int i = 0; i < V; i++)
            path[i] = -1;
 
        /* Let us put vertex 0 as the first vertex in the path.
           If there is a Hamiltonian Cycle, then the path can be
           started from any point of the cycle as the graph is
           undirected */
        path[0] = 0;
        if (hamCycleUtil(graph, path, 1) == false)
        {
            System.out.println("\nSolution does not exist");
            return 0;
        }
 
        printSolution(path);
        return 1;
    }
 
    /* A utility function to print solution */
    void printSolution(int path[])
    {
        System.out.println("Solution Exists: Following" +
                           " is one Hamiltonian Cycle");
        for (int i = 0; i < V; i++)
            System.out.print(" " + path[i] + " ");
 
        // Let us print the first vertex again to show the
        // complete cycle
        System.out.println(" " + path[0] + " ");
    }
 
    // driver program to test above function
    public static void main(String args[])
    {
        HamiltonianCycle hamiltonian =
                                new HamiltonianCycle();
        /* Let us create the following graph
           (0)--(1)--(2)
            |   / \   |
            |  /   \  |
            | /     \ |
           (3)-------(4)    */
        int graph1[][] = {{0, 1, 0, 1, 0},
            {1, 0, 1, 1, 1},
            {0, 1, 0, 0, 1},
            {1, 1, 0, 0, 1},
            {0, 1, 1, 1, 0},
        };
 
        // Print the solution
        hamiltonian.hamCycle(graph1);
 
        /* Let us create the following graph
           (0)--(1)--(2)
            |   / \   |
            |  /   \  |
            | /     \ |
           (3)       (4)    */
        int graph2[][] = {{0, 1, 0, 1, 0},
            {1, 0, 1, 1, 1},
            {0, 1, 0, 0, 1},
            {1, 1, 0, 0, 0},
            {0, 1, 1, 0, 0},
        };
 
        // Print the solution
        hamiltonian.hamCycle(graph2);
    }
}


OUTPUT:
Solution Exists: Following is one Hamiltonian Cycle
 0  1  2  4  3  0

Solution does not exist

Comments

Post a Comment

Popular posts from this blog

Solve the Sudoku Python

PROGRAM TO SOLVE SUDOKU # A Utility Function to print the Grid def print_grid(arr):      for i in range ( 9 ):          for j in range ( 9 ):              print arr[i][j],          print ( 'n' )              # Function to Find the entry in # the Grid that is still  not used # Searches the grid to find an # entry that is still unassigned. If # found, the reference parameters # row, col will be set the location # that is unassigned, and true is # returned. If no unassigned entries # remains, false is returned. # 'l' is a list  variable that has # been passed from the solve_sudoku function # to keep track of incrementation # of Rows and Columns def find_empty_location(arr, l):      for row in range ( 9 ):       ...
Read more

Solve the Sudoku Java

PROGRAM TO SOLVE SUDOKU class GFG {      public static boolean isSafe( int [][] board,                                   int row, int col,                                   int num)      {          // Row has the unique (row-clash)          for ( int d = 0 ; d < board.length; d++)          {                             // Check if the number we are trying to   ...
Read more

Find Duplicates Java

PROGRAM TO FIND REPEATING NUMBERS IN AN ARRAY class MAIN {           public static void main(String args[]) {          int numRay[] = { 0 , 4 , 3 , 2 , 7 , 8 , 2 , 3 , 1 };               for ( int i = 0 ; i < numRay.length; i++) {              numRay[numRay[i] %  numRay.length] = numRay[numRay[i] %  numRay.length] + numRay.length;          }          System.out.println( "The repeating elements are : " );          for ( int i = 0 ; i < numRay.length; i++) {              if (numRay[i] >= numRay.length* 2 ) {                ...
Read more