M Coloring Problem Backtracking Algorithm

(700 Views)

What is M Coloring Backtracking Algorithm?

In this problem, an undirected graph is given. There is also provided m colors. The problem is to find if it is possible to assign nodes with m different colors, such that no two adjacent vertices of the graph are of the same colors. If there exists a solution, then display which color is assigned on which vertex.

Starting from the vertex 0, we will try to assign colors one by one to all the different nodes. But before assigning, we have to check whether the color is safe or not. A color is not safe if the adjacent vertices are containing the same color.

Image Reference: Geeks for Geeks

M Coloring Problem Backtracking Algorithm Flowchart

Image Reference: Geeks for Geeks

M Coloring Problem Backtracking Pseudo Code

while there are untried conflagrations { generate the next configuration if there are no adjacent vertices which are colored with same color { print this configuration; } }

M Coloring Problem Implementation in Java:

public class mColoringProblem { final int V = 4; int color[]; boolean isSafe(int v, int graph[][], int color[], int c) { /*for loop with iterations */ for (int i = 0; i < V; i++) if (graph[v][i] == 1 && c == color[i]) return false; return true; } /* A recursive utility function to solve m coloring problem */ boolean graphColoringUtil(int graph[][], int m, int color[], int v) { /* base case: If all vertices are assigned a color then return true */ if (v == V) return true; /* 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 */ if (graphColoringUtil(graph, m, color, v + 1)) return true; /* If assigning color c doesn't lead to a solution then remove it */ color[v] = 0; } } /* If no color can be assigned to this vertex then return false */ return false; } /* This function solves the m Coloring problem using Backtracking. It mainly uses graphColoringUtil() to solve the problem. It returns false if the m colors cannot be assigned, otherwise return true and prints assignments of colors to all vertices. Please note that there may be more than one solutions, this function prints one of the feasible solutions.*/ boolean graphColoring(int graph[][], int m) { // Initialize all color values as 0. This // initialization is needed correct functioning // of isSafe() color = new int[V]; /* For loop with iterations */for (int i = 0; i < V; i++) color[i] = 0; // Call graphColoringUtil() for vertex 0 if (!graphColoringUtil(graph, m, color, 0)) { System.out.println("Solution does not exist"); return false; } // Print the solution printSolution(color); return true; } /* A utility function to print solution */ void printSolution(int color[]) { System.out.println("Solution Exists: Following" + " are the assigned colors"); /*for loop with iterations */ for (int i = 0; i < V; i++) System.out.print(" " + color[i] + " "); System.out.println(); } // driver program to test above function public static void main(String args[]) { mColoringProblem Coloring = new mColoringProblem(); /* Create following graph and test whether it is 3 colorable (3)---(2) | / | | / | | / | (0)---(1) */ int graph[][] = {{0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}, }; int m = 3; // Number of colors Coloring.graphColoring(graph, m); } }

Output:

Solution Exists: Following are the assigned colors 1 2 3 2