Hello Ninja🥷! In this article, we are going to understand a critical topic. But before we start, We highly recommend you have some basic knowledge of Graphs, Graphs terminologies, Greedy algorithms, clear understanding of array, functions, and basics of any programming language.
If You fulfill all the prerequisites, congrats, you are good to join us in this journey of Graph coloring using the Greedy Algorithm🙌!
Graph coloring using the Greedy Algorithm
Graph coloring using the Greedy Algorithm is the procedure of assignment of colors to each vertex of a graph G such that no adjacent vertices get the same color. The main objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph G is called the chromatic number of that graph. Graph coloring problem is an NP-Complete problem.
You are already getting a hint that we will do Graph coloring using the Greedy algorithm. The greedy algorithm doesn’t always use a minimum number of colors.
Examples:
1)
The graph can be colored with a maximum of two colors.
2)
The graph can be colored with a maximum of three colors. 3)
The graph can be colored with a maximum of six colors.
Algorithm
The following points explain the Graph coloring using the Greedy Algorithm:
Color the first vertex with the first color.
Follow these steps for the remaining V-1 vertices.
Think about the selected vertex.
Use the color with the lowest number to color it that hasn't been applied to any
colored vertices before surrounding it.
Assign a new color to vertex v if all previously used colors can be seen on the vertices next to it.
➡️Assign the color to the first vertex 0.
➡️Next vertex is 1, its adjacent vertex two is not colored yet, and vertex 0 is not adjacent, so we color vertex one the same color as vertex 0.
➡️Next vertex is 2. Its adjacent vertices 0,1 are colored with the same color so we will color it with a different one.
➡️Next vertex is 3, its adjacent vertex two is colored, and vertex 4 is not, so we color it with the same color as vertex 0 because it is not adjacent to 2.
➡️Next vertex is 4; as we can see, its adjacent vertices 2 and 3 are already colored, and all previously used colors appear on vertices adjacent to vertex 4, so we assign a new different color to it.
Implementation
Code in c++
#include <bits/stdc++.h>
using namespace std;
vector<int> result;// this vector tells us the i th vertex is coloured
// with result[i] colour
void graphColoring(int v,vector<vector<int>> &adj)
{
//Assign the colour to the first vertex
result.push_back(0);
// At start all the vertices are not coloured except first vertex
for (int u = 1; u < v; u++)
result.push_back(-1);
// boolean available vector tells which colour is available to
// to a particular vertex
bool available[v];
for (int clr = 0; clr < v; clr++)
available[clr] = false;
//True value of available[clr] would mean that the color clr is
// assigned to one of its adjacent vertices
for (int u = 1; u < v; u++)
{
for (int i = 0; i <v; i++){
if(adj[i][u]==1)
if (result[i] != -1)
available[result[i]] = true;
}
int clr;
for (clr = 0; clr < v; clr++)
if (available[clr] == false)
break;
result[u] = clr;
// resetting the value of available for next iteration
for (int i = 0; i <v; i++){
if(adj[i][u]==1)
if (result[i] != -1)
available[result[i]] = false;
}
}
}
int main() {
// v → no of vertices
// e → no of edges
int v,e;
cin >>v>>e;
vector<vector<int>> adj(v,vector<int>(v,0));
for(int i = 0;i<e;i++){
int a,b;cin>>a>>b;
adj[a][b] = 1;
adj[b][a] = 1;
}
graphColoring(v,adj);
cout<<"The pattern of Graph coloring using the Greedy Algorithm"<<endl;
for (int u = 0; u < v; u++)
cout << "Vertex " << u << " ---> Color "
<< result[u] << endl;
return 0;
}
You can also try this code with Online C++ Compiler
The pattern of Graph coloring using the Greedy Algorithm
Vertex 0 ---> Color 0
Vertex 1 ---> Color 0
Vertex 2 ---> Color 1
Vertex 3 ---> Color 0
Vertex 4 ---> Color 2
Complexity Analysis
Time Complexity: O(V^2)
Because we use only two nested for loops of higher limit V, making adjacency matrix and updating the result vector, where V is the total number of vertices.
Space Complexity: O(V^2)
We have created an adjacency matrix of space O(V^2) to store the information adjacent to the vertices of a vertex.
Frequently Asked Questions
What is a graph in data structure with an example?
The graph is a standard data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them. A pair (x,y) is an edge, which communicates that the x vertex connects to the y vertex.
What is a greedy algorithm in graph theory?
Greedy algorithms gather all the information related to a specific problem and then establish rules for which components to add to the solution at each algorithmic step.
What is a chromatic number in Graph coloring using the Greedy algorithm?
The fewest colors are required to color a graph's vertices so that no two neighboring vertices share the same hue.
What makes an algorithm greedy?
A greedy algorithm is a method of problem-solving that chooses the best choice at the time. It is unconcerned with whether the most excellent result at the moment will produce the final best result. Even if the option was the erroneous one, the algorithm never goes back and changes its mind. It functions in a top-down manner.
What is the application of graph coloring?
The application of graph coloring is widespread in computer science research, including data mining, picture segmentation, clustering, image capture, networking, etc.
Conclusion
In this article, we have discussed a coding problem in which we have to Graph coloring using the Greedy algorithm. We have seen the question's solution, time, and space complexity.