Scribd
Upload
21 views3 pages

Graph Coloring Problem

The document presents a C program that solves the Graph Coloring Problem using a backtracking algorithm. It defines functions to check if a color can be assigned to a vertex and to recursively assign colors to all vertices. The program takes user input for the number of vertices, colors, and the adjacency matrix, and outputs the assigned colors or indicates if no solution exists.

Uploaded by

shanne724
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views3 pages

Graph Coloring Problem

The document presents a C program that solves the Graph Coloring Problem using a backtracking algorithm. It defines functions to check if a color can be assigned to a vertex and to recursively assign colors to all vertices. The program takes user input for the number of vertices, colors, and the adjacency matrix, and outputs the assigned colors or indicates if no solution exists.

Uploaded by

shanne724
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Graph Coloring Problem

Code:

#include <stdio.h>

#include <stdbool.h>

#define MAX_VERTICES 100

bool isSafe(int graph[MAX_VERTICES][MAX_VERTICES], int color[], int v, int c, int V)

for (int i = 0; i < V; i++) {

if (graph[v][i] == 1 && color[i] == c) {

return false;

return true;

bool graphColoringUtil(int graph[MAX_VERTICES][MAX_VERTICES], int m, int color[], int v, int V)

if (v == V) {

return true;

for (int c = 1; c <= m; c++) {

if (isSafe(graph, color, v, c, V)) {

color[v] = c;

if (graphColoringUtil(graph, m, color, v + 1, V)) {

return true;

color[v] = 0;
}

return false;

bool graphColoring(int graph[MAX_VERTICES][MAX_VERTICES], int m, int V)

int color[V];

for (int i = 0; i < V; i++) {

color[i] = 0;

if (graphColoringUtil(graph, m, color, 0, V)) {

printf("Solution exists: Following are the assigned colors:\n");

for (int i = 0; i < V; i++) {

printf("Vertex %d -> Color %d\n", i + 1, color[i]);

return true;

printf("Solution does not exist\n");

return false;

void main()

int V, m;

printf("Enter the number of vertices: ");

scanf("%d", &V);

printf("Enter the number of colors: ");

scanf("%d", &m);

int graph[MAX_VERTICES][MAX_VERTICES];

printf("Enter the adjacency matrix (1 for an edge, 0 for no edge):\n");


for (int i = 0; i < V; i++) {

for (int j = 0; j < V; j++) {

printf("enter the edge of %d %d: ",i+1,j+1);

scanf("%d", &graph[i][j]);

if (!graphColoring(graph, m, V)) {

printf("No solution exists with %d colors.\n", m);

getch();

Output:

You might also like