java programming – Graph Coloring | Set 2 (Greedy Algorithm)

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.
Java program:
// A Java program to implement greedy algorithm for graph coloring
import java.io.*;
import java.util.*;
import java.util.LinkedList;
 
// This class represents an undirected graph using adjacency list
class Graph
{
 private int V; // No. of vertices
 private LinkedList<Integer> adj[]; //Adjacency List
 
 //Constructor
 Graph(int v)
 {
 V = v;
 adj = new LinkedList[v];
 for (int i=0; i<v; ++i)
 adj[i] = new LinkedList();
 }
 
 //Function to add an edge into the graph
 void addEdge(int v,int w)
 {
 adj[v].add(w);
 adj[w].add(v); //Graph is undirected
 }
 
 // Assigns colors (starting from 0) to all vertices and
 // prints the assignment of colors
 void greedyColoring()
 {
 int result[] = new int[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
 boolean available[] = new boolean[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
 Iterator<Integer> it = adj[u].iterator() ;
 while (it.hasNext())
 {
 int i = it.next();
 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
 it = adj[u].iterator() ;
 while (it.hasNext())
 {
 int i = it.next();
 if (result[i] != -1)
 available[result[i]] = false;
 }
 }
 
 // print the result
 for (int u = 0; u < V; u++)
 System.out.println("Vertex " + u + " ---> Color "
 + result[u]);
 }
 
 // Driver method
 public static void main(String args[])
 {
 Graph g1 = new Graph(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);
 System.out.println("Coloring of graph 1");
 g1.greedyColoring();
 
 System.out.println();
 Graph g2 = new Graph(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);
 System.out.println("Coloring of graph 2 ");
 g2.greedyColoring();
 }
}

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