Graph Coloring | Set 2 (Greedy Algorithm) - GeeksforGeeks

Graph Coloring | Set 2 (Greedy Algorithm) - GeeksforGeeks
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.

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.

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;

        for (i = adj[u].begin(); i != adj[u].end(); ++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

        for (i = adj[u].begin(); i != adj[u].end(); ++i)

            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;

}

Here d is the maximum degree in the given graph. Since d is maximum degree, a vertex cannot be attached to more than d vertices. When we color a vertex, at most d colors could have already been used by its adjacent. To color this vertex, we need to pick the smallest numbered color that is not used by the adjacent vertices. If colors are numbered like 1, 2, …., then the value of such smallest number must be between 1 to d+1 (Note that d numbers are already picked by adjacent vertices).
Read full article from Graph Coloring | Set 2 (Greedy Algorithm) - GeeksforGeeks