Graph Coloring Algorithm using Backtracking

Algorithm

What is Graph Coloring Problem?

We have been given a graph and we are asked to color all vertices with the ‘M’ number of given colors, in such a way that no two adjacent vertices should have the same color.

Graph coloring problem

It it is possible to color all the vertices with the given colors then we have to output the colored result, otherwise output ‘no solution possible’.

The least possible value of ‘m’ required to color the graph successfully is known as the chromatic number of the given graph.

Graph Coloring Solution

Using Naive Algorithm

In this approach using the brute force method, we find all permutations of color combinations that can color the graph.

If any of the permutations is valid for the given graph and colors, we output the result otherwise not.

This method is not efficient in terms of time complexity because it finds all colors combinations rather than a single solution.

Using Backtracking Algorithm

The backtracking algorithm makes the process efficient by avoiding many bad decisions made in naïve approaches.

In this approach, we color a single vertex and then move to its adjacent (connected) vertex to color it with different color.

After coloring, we again move to another adjacent vertex that is uncolored and repeat the process until all vertices of the given graph are colored.

In case, we find a vertex that has all adjacent vertices colored and no color is left to make it color different, we backtrack and change the color of the last colored vertices and again proceed further.

If by backtracking, we come back to the same vertex from where we started and all colors were tried on it, then it means the given number of colors (i.e. ‘m’) is insufficient to color the given graph and we require more colors (i.e. a bigger chromatic number).

Graph coloring problem algorithm

Steps To color graph using the Backtracking Algorithm:

  1. Different colors:
    1. Confirm whether it is valid to color the current vertex with the current color (by checking whether any of its adjacent vertices are colored with the same color).
    2. If yes then color it and otherwise try a different color.
    3. Check if all vertices are colored or not.
    4. If not then move to the next adjacent uncolored vertex.
  2. If no other color is available then backtrack (i.e. un-color last colored vertex).

Here backtracking means to stop further recursive calls on adjacent vertices by returning false. In this algorithm Step-1.2 (Continue) and Step-2 (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.

Here is the solution to the graph coloring problem in C and Java using the backtracking algorithm:

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//Number of vertices
#define numOfVertices 4

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

//Vertex
typedef struct{
    char name;
    bool colored;
    int color;
} Vertex;

//VertexList
Vertex *vertexArray[numOfVertices];

//function check if a vertex has any uncolored neighbors
int hasUncoloredNeighbours(int idx){
  for(int i=0;i<numOfVertices; i++){
    if(graph[idx][i] == 1 && vertexArray[i]->colored == false)
      return i;
  }
  return -1;
}

//Function to check whether it is valid to color with color[colorIndex]
 bool canColorWith(int colorIndex, int vertex) {
    Vertex *neighborVertex;
    for(int 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;
}

//function to color the vertex
bool setColors(int idx){
  int colorIndex, unColoredIdx;

    //Step: 1
    for (colorIndex=0; colorIndex<color_used; colorIndex++){
      // Step-1.1 : checking validity
      if(!canColorWith(colorIndex, idx)) continue; 

      //Step-1.2 : coloring
      vertexArray[idx]->color =  colorIndex;
      vertexArray[idx]->colored = true;
      colorCount++;

      //Step-1.3 : Whether all vertices colored?
      if(colorCount == numOfVertices ) //Base Case
          return true;

      //Step-1.4 : Next uncolored vertex
      while((unColoredIdx = hasUncoloredNeighbours(idx)) != -1){
        if(setColors(unColoredIdx))
          return true;
      }

    }

    // Step-2 : Backtracking
    vertexArray[idx]->color = -1;
    vertexArray[idx]->colored = false;
    return false;
}


int main()
{
  //define Vertex
  Vertex vertexA, vertexB, vertexC, vertexD;
  vertexA.name = 'A';
  vertexB.name = 'B';
  vertexC.name = 'C';
  vertexD.name = 'D';

  //add veritces to the array
  vertexArray[0] = &vertexA;
  vertexArray[1] = &vertexB;
  vertexArray[2] = &vertexC;
  vertexArray[3] = &vertexD;

  //set default values (uncolor) for all vertices
  for(int i=0; i<numOfVertices;i++){
    vertexArray[i]->colored = false;
    vertexArray[i]->color = -1;
  }

  //start coloring with first vertex
  bool hasSolution = setColors(0);

  //check if all vertices was successfully colored
  if (!hasSolution)
      printf("No Solution");
  else {
      for(int i=0; i<numOfVertices;i++){
          printf("%c %s \n",vertexArray[i]->name,colors[vertexArray[i]->color]);
      }
  }

  return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

class Vertex {
  String name;
  List<Vertex> adjacentVertices;
  boolean colored;
  String color;

  public Vertex(String name) {
    this.name = name;
    this.adjacentVertices = new ArrayList<>();
    this.colored =false;
    this.color = "";
  }

  //connect two verticess bi-directional
  public void addNeighbor(Vertex vertex){
    this.adjacentVertices.add(vertex);
    vertex.adjacentVertices.add(this);
  }
}

class Coloring {
  String colors[];
  int colorCount;
  int numberOfVertices;

  public Coloring(String[] colors, int N) {
    this.colors = colors;
    this.numberOfVertices = N;
  }

  public boolean setColors(Vertex vertex){
    //Step: 1
    for(int colorIndex=0; colorIndex<colors.length; colorIndex++){ 
      //Step-1.1: checking validity
      if(!canColorWith(colorIndex, vertex)) 
        continue; 

      //Step-1.2: continue coloring 
      vertex.color=colors[colorIndex]; 
      vertex.colored=true; 
      colorCount++; 

      //Step-1.3: check whether all vertices colored? 
      if(colorCount== numberOfVertices) //base case 
        return true; 

      //Step-1.4: next uncolored vertex 
      for(Vertex nbrvertex: vertex.adjacentVertices){ 
        if (!nbrvertex.colored){ 
          if(setColors(nbrvertex))
            return true;
          } 
      }

    }
      
    //Step-4: backtrack 
    vertex.colored = false;
    vertex.color = "";
    return false;
  } 

  //Function to check whether it is valid to color with color[colorIndex]
  boolean canColorWith(int colorIndex, Vertex vertex) {
    for(Vertex nbrvertex: vertex.adjacentVertices){
      if(nbrvertex.colored && nbrvertex.color.equals(colors[colorIndex]))
        return  false;
    }
    return true;
  }
}
                    
public class Main{
  public static void main(String args[]){ 
    //define vertices
    Vertex vertices[]= {new Vertex("A"), new Vertex("B"), new Vertex("C"), new Vertex("D")};

    //join verices
    vertices[0].addNeighbor(vertices[1]);
    vertices[1].addNeighbor(vertices[2]);
    vertices[2].addNeighbor(vertices[3]);
    vertices[0].addNeighbor(vertices[3]);

    //define colors
    String colors[] = {"Green","Blue"};

    //create coloring object
    Coloring coloring = new Coloring(colors, vertices.length);

    //start coloring with vertex-A
    boolean hasSolution = coloring.setColors(vertices[0]);

    //check if coloring was successful
    if (!hasSolution)
        System.out.println("No Solution");
    else {
        for (Vertex vertex: vertices){
            System.out.println(vertex.name + " "+ vertex.color +"\n");
        }
    }
  }
}

Output:

graph coloring problem using backtracking example-min

Note: Tb backtrack, we are returning false. By doing so the program comes back to the 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.

In the above program, we have created the same graph as depicted in the first picture and successfully colored the graph using the backtracking algorithm.

4 thoughts on “Graph Coloring Algorithm using Backtracking”

  1. Hello,

    I am learning the graph algorithm and I liked your program very much.
    I have GitHub Repository that contains my learning and study on the topic.
    Can I have include your program on my GitHub Repository with the link as the reference and the author within my program?

Leave a Reply

Your email address will not be published. Required fields are marked *