graph coloring

Algorithm For Graph Coloring

We have discussed some basic applications of Graph Traversal and now’s it time to learn some new Graph concepts i.e Algorithm of graph coloring.

In this post, we are going to discuss the algorithm of Graph Coloring and some problems based on it. So, let’s start.

What is Graph Coloring ..?

Graph coloring is a method to color the graph with different colors such that no two adjacent nodes have the same color.

For example,

algorithm of Biparttite graph

Now we have to color the Graph such that no two neighboring vertexes have the same color.

algorithm of Biparttite graph

This way we can color the Graph.

NOTE minimum color required to color the Graph is 3 but we can color it with more colors as well.

The minimum color required to color a Graph is called its Chromatic Number.

Applications of Graph Coloring

Scheduling : Graph Coloring is useful in scheduling problems since once person can be assigned to one job for particular time slot so, here Graph Coloring helps us.

For example, during examinations too some papers of different departments are common so two schedule them such that every student from every department can get a particular slot for it. Here also Graph Coloring comes to play.

Geographical Maps : To manage traffics Graph coloring is helpful.

Pattern Matching : The problem of coloring a graph arises in many practical areas such as designing seating plans and solving Sudoku puzzles.

These are some of the applications now let’s discuss some problems based on it in Graph.

Leetcode 785: Is Graph Bipartite

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:

0----1
|    |
|    |
3----2

We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:

0----1
| \  |
|  \ |
3----2

We cannot find a way to divide the set of nodes into two independent subsets.

Note :

  • graph will have a length in the range [1, 100].
  • graph[i] will contain integers in the range [0, graph.length – 1].
  • graph[i] will not contain or duplicate values.
  • The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

Analysis of Problem Statement

In the above problem, we have to find if the given graph is Bipartite or not.

Before that, let’s understand what is a Bipartite Graph..?

Bipartite Graph

A Bipartite Graph is a graph whose vertices can be divided into two disjoint sets so that every edge connects two vertices from different sets. In simple words, there are no edges which connect vertices from the same set, both sets are independent.

Let’s understand it by an example,

algorithm of Biparttite graph

Above Graph is a Bipartite Graph as we can divide vertices of the above Graph into two disjoint set.

Bipartite graph

NOTE no edge connect vertices to two same set and that’s how the above Graph is a Bipartite Graph.

Let’s see another example,

Graph

Find out whether above Graph is Bipartite or not and comment it below.

Hope Problem Statement is clear, we just have to find whether a Graph is Bipartite or not.

Approach to the Problem

There are many approaches to this problem but we will solve it via Graph Coloring and it is the easiest way to solve it.

So, let see the approach.

If you observe carefully, Bipartite Graph can be colored by at most two colors and it’s obvious because vertex of every edge belongs to different sets, so we always have the option to color one vertex with one color and other with different color.

And if any Graph cannot be colored with at most two colors then, that Graph is not Bipartite.

This is the main logic of our approach, so we just have to check whether Graph needs more than two colors for coloring or not.

How to check whether a Graph is two colorable or not ..?

For this DFS Traversal will help us, we will do a DFS Traversal and check whether coloring the neighbors of the current vertex is possible with one color or not.

If it’s possible then we will move ahead or else we will return false.

Let’s look at the Algorithm,

Algorithm for Bipartite Graph

It will be simple DFS Traversal only extra part is that we will maintain a color[] array.

Initially we will color the first vertex with random color, let’s say Red.

Now, while visiting the neighbors, we will check if color of current vertex. If color is ‘Red’, then we will color it’s neighbors with color ‘Blue’.

We will continue the above process for every vertex and if we find that coloring is not possible with only two colors then we will simply return false as the Graph is not Bipartite.

Let’s see the code,

bool dfs(vector<vector<int>>& graph, int *color, int col, bool *vis, int s)
{
    vis[s] =true;
    color[s] = col;

    for(int i = 0; i < graph[s].size(); i++)
    {
        if(vis[graph[s][i]] == false && col == 1)
        {
            if(dfs(graph, color, 2, vis, graph[s][i]) == false)
            {
                return false;
            }
        }
        else if(vis[graph[s][i]] == false && col == 2)
        {
            if(dfs(graph, color, 1, vis, graph[s][i]) == false) {
                return false;
            }
        }

        else if(color[graph[s][i]] == col) return false;
    }

    return true;
}

bool isBipartite(vector<vector<int>>& graph) {

    int n = graph.size();

    int *color = new int[n];
    bool *vis = new bool[n];

    for(int i = 0; i < n; i++){
        color[i] = -1;     
        vis[i] = false;
    }

    for(int i = 0; i < n; i++) 
    {
        if(vis[i] == false)
        {
            if(dfs(graph, color, 1, vis, i) == false) return false;
        }
    }

    return true;
}

In the above code, col = 1 represent ‘Red’ and col = 2 represent blue.

Please observe the conditions in the dfs() function. If current color is 1, then we color neighbors with color 2 and vice versa.

If we find that color of current node and neighbor node is same then, it is sure that Graph cannot be a bipartite Graph.

Hope code and logic behind Coloring of Graph is clear to you. We will continue with Graph in the next post as well.
Hope you understand the Algorithm for Graph Coloring
That’s all folks..!!!
More Problems : Possible Bipartition

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

1 Comment

Leave a Comment

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