Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Explanation
2.2.
Algorithm
2.3.
Code
2.4.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the Chromatic Number?
3.2.
When is it beneficial to use an adjacency matrix instead of an adjacency list?
3.3.
What is the time complexity of the DSatur Algorithm?
4.
Conclusion
Last Updated: Mar 27, 2024

DSatur Algorithm for Graph Coloring

Author Ujjawal Gupta
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In this blog, we will discuss a problem based on graph coloring. Graphs-based coding problems are widely asked in competitive programming contests and various coding interviews. Here we will discuss the DSatur algorithm for graph coloring. The DSatur algorithm is the most efficient algorithm for graph coloring.

Problem Statement

You are given a graph with ‘V’ vertices and ‘E’ edges connecting them. Your task is to color all the vertices such that it satisfies the following two conditions:

  • The pair of adjacent vertices will always be of different colors.
  • The count of different colors should be minimum.

Explanation

Before moving further, we need to understand what is a chromatic number. The minimum number of colors required to color the graph such that adjacent vertices have different colors is known as the chromatic number, denoted by X(G). Here, we need to calculate the chromatic number of the given graph. For example, we need three different colors to color all the vertices in the following diagram. Hence, the chromatic number of the given graph is 3.
 

Colored Graph

The brute force for this problem is less efficient and very complex to implement as we need to check each possible coloring and optimally find the minimum out of them. Therefore we need to find it optimally using the DSatur algorithm. Let’s start with the DSatur algorithm, 

DSatur Algorithm abbreviated from “degree of saturation algorithm.” It is based on the Greedy Algorithm. The count of different colors assigned to the adjacent vertices of the given vertex is known as its saturation degree.

Algorithm

The DSatur algorithm is as follows:

  • Select uncolored vertex ‘V’ among all uncolored vertex whose saturation degree is maximum. If two or more vertices have the same saturation degree, select one with the maximum degree subgraph induced by the uncolored graph.
  • Find the smallest integer between 0 to ‘V’, which is not assigned to its neighbor vertices, and assign that color to the vertex ‘V’. This integer value represents the color of that vertex.
  • Repeat the above steps for all the vertices.

Code

// Program for DSatur Algorithm for graph coloring.
#include <iostream>
#include <vector>
#include <set>
#include <tuple>
using namespace std;

// Function to add edge between two vertices.
void addEdgeBetween(vector<int> graph[], int a, int b)
{
    graph[a].push_back(b);
    graph[b].push_back(a);
}
 
// For storing information related to vertices.
class vertexInfo
{
public:
    // Saturation degree of the vertex.
    int sat;

    // degree in uncolored graph
    int deg;
 
    // index of vertex.
    int vertex;
};
 
struct maxSat
{
    bool operator()(const vertexInfo &lhs,
                    const vertexInfo &rhs) const
    {
        return tie(lhs.sat, lhs.deg, lhs.vertex) > tie(rhs.sat, rhs.deg, rhs.vertex);
    }
};

// Function to print color of each vertex of graph.
void printcolor(vector<int> &color)
{
    for (int i = 0; i < color.size(); i++)
    {
        cout << "The Color of the vertex " << i << " is " << color[i] << endl;
    }
}
 
// Function for DSatur algo.
int DSatur(vector<int> graph[], int V)
{
    int u, i;
    // Create vector to store status of used colors.
    vector<bool> use(V, false);

 
    // Create vector to store colors.
    vector<int> color(V), d(V);
    vector<set<int>> adjCols(V);
    set<vertexInfo, maxSat> Q;
    set<vertexInfo, maxSat>::iterator maxPtr;

    for (u = 0; u < V; u++)
    {
        color[u] = -1;
        d[u] = graph[u].size();
        adjCols[u] = set<int>();
        Q.emplace(vertexInfo{0, d[u], u});
    }
 
    while (!Q.empty())
    {
        maxPtr = Q.begin();
        u = (*maxPtr).vertex;
        Q.erase(maxPtr);
 
        for (int v : graph[u])
            if (color[v] != -1)
                use[color[v]] = true;
        i = 0;
        while (i != use.size())
        {
            if (use[i] == false)
                break;
            i++;
        }
        for (auto v : graph[u])
            if (color[v] != -1)
                use[color[v]] = false;

        color[u] = i;
        for (auto v : graph[u])
        {
            if (color[v] == -1)
            {
                Q.erase(
                    {int(adjCols[v].size()),
                     d[v], v});
                adjCols[v].insert(i);
                d[v]--;
                Q.emplace(vertexInfo{
                    int(adjCols[v].size()),
                    d[v], v});
            }
        }
    }
    set<int> ans;
    for (int i = 0; i < V; i++)
        ans.insert(color[i]);
 
    printcolor(color);
    // Return Chromatic number.
 
    // Print the Chromatic number of graph coloring.
    cout << "The Chromatic number is : ";
    return ans.size();
}
 
// Function to calculate Chromatic numvber.
int getChromaticNumber()
{ 
    // Input number of vertices 'V' and edges 'E'.
    int V, E;
    cin >> V >> E;
 
    // Create graph of ‘V’ vertices from 0 to V - 1.
    vector<int> graph[V];
    for (int i = 0; i < E; i++)
    { 
        // Input edge from vertex 'A' to vertex 'B'.
        int a, b;
        cin >> a >> b;
 
        // Insert edge between the vertices.
        addEdgeBetween(graph, a, b);
    }
    return DSatur(graph, V);
}

int main()
{
    cout << getChromaticNumber();
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

5 7
1 2
0 3
4 1 
2 1 
4 2 
1 3
4 2

Output

The Color of the  vertex 0 is 1
The Color of vertex 1 is 1
The Color of vertex 2 is 0
The Color of vertex 3 is 0
The Color of vertex 4 is 2
The chromatic number is : 3

Complexity Analysis

Time Complexity

O((V + E) * log(V)), where ‘V’ is the number of vertices, and ‘E’ is the number of Edges.

As traversing of adjacency list takes O(V+E) and searching in the set takes O(log(V)).

Space Complexity

The creation of an adjacency list takes O(V+E) space where ‘V’ is the number of vertices, and ‘E’ is the total number of edges. Hence, its space complexity is O(V+E)

Frequently Asked Questions

What is the Chromatic Number?

The minimum number of colors required to color the graph such that adjacent vertices have different colors is known as the chromatic number, denoted by X(G)

When is it beneficial to use an adjacency matrix instead of an adjacency list?

Adjacency Matrix is used for the representation of a dense graph whereas an adjacency list is used to represent the sparse graphs

What is the time complexity of the DSatur Algorithm?

The time complexity of the DSatur Algorithm is O((V+E)*log(V)) where ‘V’ is the number of vertices and ‘E’ is the number of Edges.

Conclusion

In this blog, we have learned graph coloring, chromatic numbers, and the DSatur algorithm for graph coloring, the most efficient algorithm for graph coloring. If you want to explore graph coloring, visit M-Coloring Problem.

Recommended Readings


Hence learning never stops, and there is a lot more to learn.

Do check out some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Live masterclass