Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Graph Coloring

Explore the greedy algorithm technique for solving graph coloring problems. This lesson helps you understand how to assign colors efficiently to graph vertices while avoiding conflicts, and analyze the algorithm's time complexity. Gain practical insights to tackle similar interview challenges in C++.

We'll cover the following...

Solution: Greedy Approach

C++
#include "Graph.h"
void Graph::greedyColoring() {
  int * result = new int[this -> vertices];
  // Assign the first color to first vertex 
  result[0] = 0;
  // Initialize remaining V-1 vertices as unassigned 
  for (int u = 1; u < this -> vertices; u++)
    result[u] = -1; // no color is assigned to u 
  bool available[this -> vertices];
  for (int color = 0; color < this -> vertices; color++)
    available[color] = false;
  // Assign colors to remaining V-1 vertices 
  for (int u = 1; u < this -> vertices; u++) {
    list < int > ::iterator i;
    for (i = adjacencyList[u].begin(); i != adjacencyList[u].end(); ++i)
      if (result[ * i] != -1)
        available[result[ * i]] = true;
    // Find the first available color 
    int color;
    for (color = 0; color < this -> vertices; color++)
      if (available[color] == false)
        break;
    result[u] = color; // Assign the found color 
    // Reset the values  
    for (i = adjacencyList[u].begin(); i != adjacencyList[u].end(); ++i)
      if (result[ * i] != -1)
        available[result[ * i]] = false;
  }
  for (int u = 0; u < this -> vertices; u++)
    cout << "Vertex " << u << " ---> Color " <<
    result[u] << endl;
  
  delete result;
}
int main() {
  Graph g1(5);
  g1.addEdge(0, 1);
  g1.addEdge(0, 2);
  g1.addEdge(1, 2);
  g1.addEdge(1, 3);
  g1.addEdge(2, 3);
  g1.addEdge(3, 4);
  cout << "Coloring of graph 1 \n";
  g1.greedyColoring();
  Graph g2(5);
  g2.addEdge(0, 1);
  g2.addEdge(0, 2);
  g2.addEdge(1, 2);
  g2.addEdge(1, 4);
  g2.addEdge(2, 4);
  g2.addEdge(4, 3);
  cout << "\nColoring of graph 2 \n";
  g2.greedyColoring();
  return 0;
}

The solution is simple: assign the first available color, and keep that color as unavailable for the adjacent vertices.

Pseudocode

GreedyColoring()
  Color first vertex u with the first color.
  Do 
  {
     if color != previously colored vertices adjacent to it:
        color current v with lowest numbered color
...