Overview

This program implements a greedy algorithm to color a graph using the minimum number of colors. The goal is to ensure that no two adjacent vertices share the same color. This problem is known as the graph coloring problem, which is a well-known NP-hard problem.

Program Structure

1. Graph Representation: The graph is represented using an adjacency matrix.
2. Greedy Coloring Function: A function is used to assign colors to the vertices based on the available colors for adjacent vertices.
3. Main Function: This function initializes the graph, calls the coloring function, and prints the results.

Code Implementation

#include 
#include 

#define V 5 // Number of vertices in the graph

// Function to check if the current color assignment is safe for vertex v
int isSafe(int v, int graph[V][V], int color[], int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && color[i] == c) {
            return 0; // Color c is not safe
        }
    }
    return 1; // Color c is safe
}

// Function to color the graph
void greedyColoring(int graph[V][V]) {
    int color[V]; // Array to store colors assigned to vertices
    for (int i = 0; i < V; i++) {
        color[i] = -1; // Initialize all vertices as uncolored
    }

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

    // Assign colors to remaining vertices
    for (int u = 1; u < V; u++) {
        // Check the availability of colors
        int available[V];
        for (int i = 0; i < V; i++) {
            available[i] = 1; // Mark all colors as available
        }

        // Mark colors of adjacent vertices as unavailable
        for (int i = 0; i < V; i++) {
            if (graph[u][i] && color[i] != -1) {
                available[color[i]] = 0; // Mark color[i] as unavailable
            }
        }

        // Find the first available color
        for (int c = 0; c < V; c++) {
            if (available[c]) {
                color[u] = c; // Assign the color to vertex u
                break;
            }
        }
    }

    // Print the result
    printf("Vertex Color\n");
    for (int i = 0; i < V; i++) {
        printf("  %d       %d\n", i, color[i]);
    }
}

// Main function
int main() {
    // Example graph represented as an adjacency matrix
    int graph[V][V] = {
        {0, 1, 1, 1, 0},
        {1, 0, 0, 1, 0},
        {1, 0, 0, 1, 1},
        {1, 1, 1, 0, 1},
        {0, 0, 1, 1, 0}
    };

    greedyColoring(graph); // Call the coloring function
    return 0;
}

How to Compile and Run

To compile and run this program, follow these steps:

1. 1. Open a terminal.
   2. Save the code to a file named graph_coloring.c.
   3. Compile the program using the following command:

gcc graph_coloring.c -o graph_coloring

1. 1. Run the compiled program:

./graph_coloring

Conclusion

This program demonstrates a simple yet effective approach to solving the graph coloring problem using a greedy algorithm. While this method does not guarantee the optimal solution in all cases, it serves as a practical way to achieve a valid coloring in polynomial time.

Further Reading

For more information on graph theory and algorithms, consider exploring:

• Introduction to Algorithms by Thomas H. Cormen et al.
• Graph Theory by Reinhard Diestel
• Online resources and tutorials on graph algorithms