#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;
}