# C programming – Graph Coloring | Set 2 (Greedy Algorithm)

C programming - Graph Coloring | Set 2 (Greedy Algorithm) - Graph Algorithms - It doesn’t guarantee to use minimum colors, but it guarantees an upper bound

We introduced graph coloring and applications in previous post. As discussed in the previous post, graph coloring is widely used. Unfortunately, there is no efficient algorithm available for coloring a graph with minimum number of colors as the problem is a known NP Complete problem. There are approximate algorithms to solve the problem though. Following is the basic Greedy Algorithm to assign colors. It doesn’t guarantee to use minimum colors, but it guarantees an upper bound on the number of colors. The basic algorithm never uses more than d+1 colors where d is the maximum degree of a vertex in the given graph.

Basic Greedy Coloring Algorithm:

```1. Color first vertex with first color.
2. Do following for remaining V-1 vertices.
a) Consider the currently picked vertex and color it with the
lowest numbered color that has not been used on any previously
colored vertices adjacent to it. If all previously used colors
appear on vertices adjacent to v, assign a new color to it.
C++ program
// A C++ program to implement greedy algorithm for graph coloring
#include <iostream>
#include <list>
using namespace std;

// A class that represents an undirected graph
class Graph
{
int V; // No. of vertices
public:
// Constructor and destructor
Graph(int V) { this->V = V; adj = new list<int>[V]; }
~Graph() { delete [] adj; }

// function to add an edge to graph

// Prints greedy coloring of the vertices
void greedyColoring();
};

{
adj[w].push_back(v); // Note: the graph is undirected
}

// Assigns colors (starting from 0) to all vertices and prints
// the assignment of colors
void Graph::greedyColoring()
{
int result[V];

// Assign the first color to first vertex
result[0] = 0;

// Initialize remaining V-1 vertices as unassigned
for (int u = 1; u < V; u++)
result[u] = -1; // no color is assigned to u

// A temporary array to store the available colors. True
// value of available[cr] would mean that the color cr is
// assigned to one of its adjacent vertices
bool available[V];
for (int cr = 0; cr < V; cr++)
available[cr] = false;

// Assign colors to remaining V-1 vertices
for (int u = 1; u < V; u++)
{
// Process all adjacent vertices and flag their colors
// as unavailable
list<int>::iterator i;
if (result[*i] != -1)
available[result[*i]] = true;

// Find the first available color
int cr;
for (cr = 0; cr < V; cr++)
if (available[cr] == false)
break;

result[u] = cr; // Assign the found color

// Reset the values back to false for the next iteration
if (result[*i] != -1)
available[result[*i]] = false;
}

// print the result
for (int u = 0; u < V; u++)
cout << "Vertex " << u << " ---> Color "
<< result[u] << endl;
}

// Driver program to test above function
int main()
{
Graph g1(5);
cout << "Coloring of graph 1 \n";
g1.greedyColoring();

Graph g2(5);
cout << "\nColoring of graph 2 \n";
g2.greedyColoring();

return 0;
}
Output:```
```Coloring of graph 1
Vertex 0 --->  Color 0
Vertex 1 --->  Color 1
Vertex 2 --->  Color 2
Vertex 3 --->  Color 0
Vertex 4 --->  Color 1

Coloring of graph 2
Vertex 0 --->  Color 0
Vertex 1 --->  Color 1
Vertex 2 --->  Color 2
Vertex 3 --->  Color 0
Vertex 4 --->  Color 3```
READ  Python Programming - Matrix Chain Multiplication

#### Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

X