Program:
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
// Define the maximum number of vertices in the graph
#define MAX_VERTICES 100
// Define the graph as a 2D array of size MAX_VERTICES
int graph[MAX_VERTICES][MAX_VERTICES];
// Define the number of vertices in the graph
int num_vertices;
// Define the array to store the color of each vertex
int color[MAX_VERTICES];
// Check if the given color can be assigned to the given vertex
bool is_safe(int v, int c)
{
for(int i=0; i<num_vertices; i++)
{
if(graph[v][i] && color[i] == c)
return false;
}
return true;
}
// A recursive function to color the graph using backtracking
bool graph_coloring_util(int v)
{
// Base case: all vertices are colored
if(v == num_vertices)
return true;
// Try different colors for the current vertex
for(int c=1; c<=num_vertices; c++)
{
// Check if the color can be assigned to the current vertex
if(is_safe(v, c))
{
// Assign the color to the current vertex
color[v] = c;
// Recur for the next vertex
if(graph_coloring_util(v+1))
return true;
// Backtrack: unassign the color and try the next one
color[v] = 0;
}
}
// If no color can be assigned to the current vertex, return false
return false;
}
// A function to color the graph using backtracking
void graph_coloring()
{
Initialize all colors to 0
for(int i=0; i<num_vertices; i++)
color[i] = 0;
// Color the graph using backtracking
if(graph_coloring_util(0))
{
// Print the solution
printf("Solution exists:\nThe colors of the vertices are:\n");
for(int i=0; i<num_vertices; i++)
printf("Vertex %d: Color %d\n", i, color[i]);
}
else
printf("Solution does not exist.\n");
}
// The main function
int main()
{
// Initialize the graph
printf("Enter the number of vertices in the graph (maximum %d): ", MAX_VERTICES);
scanf("%d", &num_vertices);
printf("Enter the adjacency matrix of the graph:\n");
for(int i=0; i<num_vertices; i++)
{
for(int j=0; j<num_vertices; j++)
{
scanf("%d", &graph[i][j]);
}
// Color the graph using backtracking and measure the running time
clock_t start_time, end_time;
double cpu_time_used;
start_time = clock();
graph_coloring();
end_time = clock();
cpu_time_used = ((double) (end_time - start_time)) / CLOCKS_PER_SEC;
printf("Running time: %f seconds.\n", cpu_time_used);
return 0;
}
Output:
Enter the number of vertices in the graph (maximum 100): 6
Enter the adjacency matrix of the graph:
0 2 3 0 0 0
2 0 0 4 5 0
3 0 0 0 0 7
0 4 0 0 0 0
0 5 0 0 0 0
0 0 7 0 0 0
Solution exists:
The colors of the vertices are:
Vertex 0: Color 1
Vertex 1: Color 2
Vertex 2: Color 2
Vertex 3: Color 1
Vertex 4: Color 1
Vertex 5: Color 1
Running time: 58.000000 seconds.
