 # Adjacent vertices of a graph should not have same color. (Backtracking Algorithm)

Challenging task: In a given graph with a certain number of vertices, check if the vertices can be coloured in such a way that no two adjacent vertices have a similar colour. Also, check if such a colouring can happen with utmost 'm' colours.

The value of the maximum number of colours that can be used is provided by the user as input.

Consider the following graph as an example which can be filled with utmost 3 colors.

The simplest solution for the above problem is to check for all possible combinations and return the minimum number of colours used in those combinations. Later, compare this value with user input 'm' to know whether it satisfies the user-specified conditions.

In this way, we would get (number of vertices)^m configurations which increase's complexity. Hence, Backtracking Algorithm can be used

In order to avoid this, we now use Backtracking algorithm:

In this method, we assign a safe colour to one of the vertex and check for all possible solutions.  If the solution is not up to the user-specified requirement, delete that colour for that node and move on with other colours and vertices clearing one test case with another.

If no such combinations exist, return false -1.

## C/C++ implementation of above problem using Backtracking Algorithm.

```#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 */
bool graphColoringUtil(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)
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) == true)
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.*/
bool graphColoring(bool graph[V][V], int m)
{
// Initialize all color values as 0. This initialization is needed
// correct functioning of isSafe()
int *color = new int[V];
for (int i = 0; i < V; i++)
color[i] = 0;

// Call graphColoringUtil() for vertex 0
if (graphColoringUtil(graph, m, color, 0) == false)
{
printf("Solution does not exist");
return false;
}

// Print the solution
printSolution(color);
return true;
}

/* A utility function to print solution */
void printSolution(int color[])
{
printf("Solution Exists:"
" 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
graphColoring (graph, m);
return 0;
}
```

## Java implementation of above problem using Backtracking Algorithm.

```/* Java program for solution of M Coloring problem
using backtracking */
public class mColoringProblem {
final int V = 4;
int color[];

/* A utility function to check if the current
color assignment is safe for vertex v */
boolean isSafe(int v, int graph[][], int color[],
int c)
{
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 (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 (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);
}
}
```

## Python implementation of above problem using Backtracking Algorithm.

```# Python program for solution of M Coloring
# problem using backtracking

class Graph():

def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]\
for row in range(vertices)]

# A utility function to check if the current color assignment
# is safe for vertex v
def isSafe(self, v, colour, c):
for i in range(self.V):
if self.graph[v][i] == 1 and colour[i] == c:
return False
return True

# A recursive utility function to solve m
# coloring  problem
def graphColourUtil(self, m, colour, v):
if v == self.V:
return True

for c in range(1, m+1):
if self.isSafe(v, colour, c) == True:
colour[v] = c
if self.graphColourUtil(m, colour, v+1) == True:
return True
colour[v] = 0

def graphColouring(self, m):
colour =  * self.V
if self.graphColourUtil(m, colour, 0) == False:
return False

# Print the solution
print "Solution exist and Following are the assigned colours:"
for c in colour:
print c,
return True

# Driver Code
g  = Graph(4)
g.graph = [[0,1,1,1], [1,0,1,0], [1,1,0,1], [1,0,1,0]]
m=3
g.graphColouring(m)

```

Output:

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

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`