Back to Course

Algorithm

0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
    Stacks
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 39 of 43
In Progress

Graph Coloring

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 M-colorability 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.

KodNest Capture37

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.

KodNest Capture38

Steps To Color Graph Using Backtracking Algorithm

  1. 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?
  2. If yes then color it or else try with another color.
  3. If no other color is available then backtrack i.e un-color last colored vertex and return false.
  4. After each coloring check if all vertices are colored or not. If yes then end the program by returning true, else continue.
  5. 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 Step-2 (Continue) and Step-4 (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++){
 
            // Step-1 : checking validity
            if(!canColorWith(colorIndex, idx)) continue;  //Step-2 : Continue
 
            //Step-2 : coloring
            vertexArray[idx]->color =  colorIndex;
            vertexArray[idx]->colored = true;
            colorCount++;
 
            //Step-4 : Whether all vertices colored?
            if(colorCount == numOfVertices ) //Base Case
                return true;
 
            //Step-5 : Next uncolored vertex
            while((unColoredIdx = hasUncoloredNeighbours(idx)) != -1){
                    if(setColors(unColoredIdx))
                        return true;
            }
 
        }
 
        // Step-3 : 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.

New Report

Close