Graph coloring problem involves assigning colors to certain elements of a graph subject to certain restrictions and constraints. This has found applications in numerous fields in computer science. For example:
Vertex coloring is the most commonly encountered graph coloring problem. The problem states that given m
colors, determine a way of coloring the vertices of a graph such that no two adjacent vertices are assigned same color.
Note: The smallest number of colors needed to color a graph G is called its chromatic number.
For example, the following undirected graph can be colored using minimum of 2 colors.
Hence the chromatic number of the graph is 2.
V * V
where V is the number of vertices in graph and the 2D array is the adjacency matrix representation and value graph[i][j]
is 1 if there is a direct edge from i to j, otherwise the value is 0.m
that denotes the maximum number of colors which can be used in graph coloring.graph[4][4] = {
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 0, 1 },
{ 1, 0, 1, 0 },
};
m = 3
.V
that has numbers from 1 to m. Note that color[i]
represents the color assigned to the ith vertex.false
if the graph cannot be colored with m
colors.m
colors, the total number of possible color configurations are mV. The complexity is exponential which is very huge.public class InterviewBit{
private static boolean isSafeToColor(int[][] graph, int[] color)
{
// check for every edge, if any adjacent edge has same color, return false
for (int i = 0; i < V; i++)
for (int j = i + 1; j < V; j++)
if (graph[i][j] == 1 && color[j] == color[i])
return false;
return true;
}
private static void printColorArray(int[] color){
System.out.println("Solution colors are: ")
for(int i =0;i < color.length; i++){
System.out.println(color[i]);
}
}
/**
* returns false if the m colors cannot be assigned, else,
* return true and print assignments of colors to all vertices.
* Note: There may be more than one solutions
* The function prints only one of the solutions.
* */
private static boolean graphColoring(int[][] graph, int m, int i, int[] color)
{
// if current index becomes end
if (i == V) {
// check whether its safe to color
if (isSafeToColor(graph, color)) {
//If safe, print solution array and return true
printColorArray(color);
return true;
}
return false;
}
// Assign each color from 1 to m
for (int j = 1; j <= m; j++) {
color[i] = j;
// Check for the rest vertices by recursion
if (graphColoring(graph, m, i + 1, color))
return true;
color[i] = 0;
}
return false;
}
}
public class InterviewBit {
final int V = 4;
int[] color;
boolean isSafeToColor(int v, int[][] graphMatrix, int[] color, int c)
{
//check for each edge
for (int i = 0; i < V; i++)
if (graphMatrix[v][i] == 1 && c == color[i])
return false;
return true;
}
boolean graphColorUtil(int[][] graphMatrix, int m, int[] color, int v)
{
// If all vertices are assigned a color then return true
if (v == V)
return true;
// Try different colors for vertex V
for (int i = 1;i <= m; i++)
{
// check for assignment safety
if (isSafeToColor(v, graphMatrix, color, i))
{
color[v] =i;
// recursion for checking other vertices
if (graphColorUtil(graphMatrix, m, color, v + 1))
return true;
// if color doesnt lead to solution
color[v] = 0;
}
}
// If no color can be assigned to vertex
return false;
}
void printColoringSolution(int color[])
{
System.out.println("Color schema for vertices are: ");
for (int i = 0; i < V; i++)
System.out.println(color[i]);
}
/**
* It returns false if the m colors cannot be assigned
* otherwise return true and
* print color assignment result to all vertices.
*/
boolean graphColoring(int[][] graphMatrix, int m)
{
// Initialize all color values as 0.
color = new int[V];
Arrays.fill(color,0);
// Call graphColorUtil() for vertex 0
if (!graphColorUtil(graphMatrix, m, color, 0))
{
System.out.println(
"Color schema not possible");
return false;
}
// Print the color schema of vertices
printColoringSolution(color);
return true;
}
// Main driver program
public static void main(String args[])
{
InterviewBit interviewBit
= new InterviewBit();
int graphMatrix[][] = {
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 0, 1 },
{ 1, 0, 1, 0 },
};
int m = 3; // Number of colors
interviewBit.graphColoring(graphMatrix, m);
}
}
Log In using