Algorithm

Getting Started with AlgorithmWhat is an Algorithm?

Characteristics of Algorithm1 Topic

Analysis Framework

Performance Analysis3 Topics

Mathematical Analysis2 Topics

Sorting AlgorithmSorting Algorithm10 Topics

Searching Algorithm6 Topics

Fundamental of Data StructuresStacks

Queues

Graphs

Trees

Sets

Dictionaries

Divide and ConquerGeneral Method

Binary Search

Recurrence Equation for Divide and Conquer

Finding the Maximum and Minimum

Merge Sort

Quick Sort

Stassen’s Matrix Multiplication

Advantages and Disadvantages of Divide and Conquer

Decrease and ConquerInsertion Sort

Topological Sort

Greedy MethodGeneral Method

Coin Change Problem

Knapsack Problem

Job Sequencing with Deadlines

Minimum Cost Spanning Trees2 Topics

Single Source Shortest Paths1 Topic

Optimal Tree Problem1 Topic

Transform and Conquer Approach1 Topic

Dynamic ProgrammingGeneral Method with Examples

Multistage Graphs

Transitive Closure1 Topic

All Pairs Shortest Paths6 Topics

BacktrackingGeneral Method

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
Participants2253
What is Graph Coloring Problem?
We have been given a graph and is asked to color all vertices with ‘m‘ given colors in such a way that no two adjacent vertices should have the same color. This graph coloring problem is also known as Mcolorability decision problem.
The M – colorability optimization problem deals with the smallest integer m for which the graph G can be colored. The integer is known as a chromatic number of the graph.
The least possible value of ‘m‘ required to color the graph successfully is known as the chromatic number of the given graph.
Let’s understand and how to solve graph coloring problem?
Graph Coloring Algorithm
Naive Algorithm
In this approach we first find all permutations of colors possible to color every vertex of the graph using Brute Force Method. Clearly if there is a large number of vertices, more the time it will take.
Bactracking Algorithm
Backtracking algorithm makes the process to solve the problem more efficient by avoiding much bad decision that needed to be made in the naive approach.
We start by coloring a single vertex, then we move to its adjacent vertex. We color it with that color which has not been used to color any of its connected vertices. After coloring it we then move to its adjacent vertex which is uncolored. We repeat the process until all vertices of the given graph are colored.
In case we find for a vertex that all its adjacent (connected) are colored with different colors and no color is left to make it color different from them, then it means the given number of colors i.e ‘m’, is insufficient to color the graph. Hence we require more colors i.e bigger chromatic number.
Steps To Color Graph Using Backtracking Algorithm
 Confirm whether it is valid to color the vertex with current color? by checking whether any of its adjacent vertices are colored with the same color?
 If yes then color it or else try with another color.
 If no other color is available then backtrack i.e uncolor last colored vertex and return false.
 After each coloring check if all vertices are colored or not. If yes then end the program by returning true, else continue.
 Now select any one of the uncolored adjacent vertices of the current colored vertex and repeat the whole process
Here backtracking means to stop further recursive calls on adjacent vertices by returning false. In this algorithm Step2 (Continue) and Step4 (backtracking) is causing the program to try different color option.
Continue – try a different color for current vertex.
Backtrack – try a different color for last colored vertex
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//Number of vertices
#define numOfVertices 4
//function Prototypes
bool canColorWith(int , int );
// 0  Green
// 1  Blue
char colors[][30] = {"Green","Blue"};
int color_used = 2;
int colorCount;
//Graph connections
int graph[numOfVertices][numOfVertices] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}};
typedef struct{
char name;
bool colored;
int color;
} Vertex;
//VertexList
Vertex *vertexArray[numOfVertices];
int hasUncoloredNeighbours(int idx){
int i;
for(i=0;i<numOfVertices; i++){
if(graph[idx][i] == 1 && vertexArray[i]>colored == false)
return i;
}
return 1;
}
bool setColors(int idx){
int colorIndex, unColoredIdx;
for (colorIndex=0; colorIndex<color_used; colorIndex++){
// Step1 : checking validity
if(!canColorWith(colorIndex, idx)) continue; //Step2 : Continue
//Step2 : coloring
vertexArray[idx]>color = colorIndex;
vertexArray[idx]>colored = true;
colorCount++;
//Step4 : Whether all vertices colored?
if(colorCount == numOfVertices ) //Base Case
return true;
//Step5 : Next uncolored vertex
while((unColoredIdx = hasUncoloredNeighbours(idx)) != 1){
if(setColors(unColoredIdx))
return true;
}
}
// Step3 : Backtracking
vertexArray[idx]>color = 1;
vertexArray[idx]>colored = false;
return false;
}
//Function to check whether it is valid to color with color[colorIndex]
bool canColorWith(int colorIndex, int vertex) {
Vertex *neighborVertex;
int i;
for(i=0; i<numOfVertices; i++){
//skipping if vertex are not connected
if(graph[vertex][i] == 0) continue;
neighborVertex = vertexArray[i];
if(neighborVertex>colored && neighborVertex>color == colorIndex)
return false;
}
return true;
}
int main()
{
int i;
//Creating Vertex
Vertex vertexA, vertexB, vertexC, vertexD;
vertexA.name = 'A';
vertexB.name = 'B';
vertexC.name = 'C';
vertexD.name = 'D';
vertexArray[0] = &vertexA;
vertexArray[1] = &vertexB;
vertexArray[2] = &vertexC;
vertexArray[3] = &vertexD;
for(i=0; i<numOfVertices;i++){
vertexArray[i]>colored = false;
vertexArray[i]>color = 1;
}
bool hasSolution = setColors(0);
if (!hasSolution)
printf("No Solution");
else {
for(i=0; i<numOfVertices;i++){
printf("%c %s \n",vertexArray[i]>name,colors[vertexArray[i]>color]);
}
}
return 0;
}
Note: For backtracking, we are returning false to rerun last recursive call to change the color of the last colored vertex. If false is returned by the starting vertex then it means there is no solution.
Complexity Analysis:
 Time Complexity: O(m^V).
There are total O(m^V) combination of colors. So time complexity is O(m^V). The upperbound time complexity remains the same but the average time taken will be less.  Space Complexity: O(V).
To store the output array O(V) space is required.