Hamiltonion Cycle

// hamiltionian cycle - backtracking

#include<stdio.h>
#include<conio.h>

// ttl vertices
#define V 5
void printSolution(int path[]);

bool isSafe(int v, bool graph[V][V], int path[], int pos)
{
        // check if added vertex is adjacent vertex of previously added vertex
    if (graph[path[pos - 1]][v] == 0)
        return false;

    // check if vertex has already been included
    for (int i = 0; i < pos; ++i)
    if (path[i] == v) return false;

    return true;
}

bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
    //base case
    if (pos == V)
    {
        if (graph[path[pos - 1]][path[0]] == 1) // if there exist an edge bw last included to firstvertex
            return true;
        else
            return false;


    }

    //try different verticies as next candidate in hamiltonian cycle
    for (int v = 1; v < V; ++v)
    {
        if (isSafe(v, graph, path, pos))
        {
            path[pos] = v;
            //recur to contruct rest of the path
            if (hamCycleUtil(graph, path, pos + 1) == true)
                return true;

            //else backtrack
            path[pos - 1];
        }

    }

    //if no vertex can be added to cycle ,return false
    return false;
}


bool hamCycle(bool graph[V][V])
{
    int *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)
    {
        printf("\nSolution does not exist");
        return false;
    }

    printSolution(path);
    return true;
}

/* A utility function to print solution */
void printSolution(int path[])
{
    printf("Solution Exists:"
        " Following is one Hamiltonian Cycle \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", path[i]);

    //  print the first vertex again to show the complete cycle
    printf(" %d ", path[0]);
    printf("\n");
}

// driver program to test above function
int main()
{
    /* Let us create the following graph
    (0)--(1)--(2)
    |   / \   |
    |  /   \  |
    | /     \ |
    (3)-------(4)    */
    bool graph1[V][V] = { { 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
    hamCycle(graph1);

    /* Let us create the following graph
    (0)--(1)--(2)
    |   / \   |
    |  /   \  |
    | /     \ |
    (3)       (4)    */
    bool graph2[V][V] = { { 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
    hamCycle(graph2);
    getchar();
    return 0;
}