gyanisherlock / backtracking Goto Github PK

#include <stdio.h>

// Number of vertices in the graph #define V 4

void printSolution(int color[]);

/* A utility function to check if the current color assignment is safe for vertex v */ bool isSafe(int v, bool graph[V][V], int color[], int c) { for (int i = 0; i < V; i++) if (graph[v][i] && c == color[i]) return false; return true; }

/* A recursive utility function to solve m coloring problem / void graphColoring(bool graph[V][V], int m, int color[], int v) { / base case: If all vertices are assigned a color then return true */ if (v == V) { printSolution(color); return; }

/* Consider this vertex v and try different colors */
for (int c = 1; c <= m; c++)
{
    /* Check if assignment of color c to v is fine*/
    if (isSafe(v, graph, color, c))
    {
        color[v] = c;

        /* recur to assign colors to rest of the vertices */
        graphColoring(graph, m, color, v + 1);

        /* If assigning color c doesn't lead to a solution
           then remove it */
        color[v] = 0;
    }
}

}

/* A utility function to print solution */ void printSolution(int color[]) { printf(" Following are the assigned colors \n"); for (int i = 0; i < V; i++) printf(" %d ", color[i]); printf("\n"); }

// driver program to test above function int main() { /* Create following graph and test whether it is 3 colorable (3)---(2) | / | | / | | / | (0)---(1) */ bool graph[V][V] = { {0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}, }; int m = 3; // Number of colors

int color[V];

for (int i = 0; i < V; i++)
    color[i] = 0;

graphColoring(graph, m, color, 0);
return 0;

}