Scribd
Upload
24 views3 pages

Graph Coloring Algorithm in C

The document contains code for graph coloring. It defines functions to check if a color assignment is safe, recursively try all color combinations, and perform graph coloring. The main function takes input for the number of vertices and edges to create an adjacency matrix, then the number of colors, and calls the graph coloring function.

Uploaded by

Pillai Maridas
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
24 views3 pages

Graph Coloring Algorithm in C

The document contains code for graph coloring. It defines functions to check if a color assignment is safe, recursively try all color combinations, and perform graph coloring. The main function takes input for the number of vertices and edges to create an adjacency matrix, then the number of colors, and calls the graph coloring function.

Uploaded by

Pillai Maridas
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

Name: Shreya ingle Roll.

No: 21102A0041 SE CMPN A

Graph Coloring:
#include <stdio.h>

int V;

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

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

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

return 0;

return 1;

int colour(int graph[V][V], int m,int color[], int v) {

if (v == V)

return 1;

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

if (isSafe(

v, graph, color, c)) {

color[v] = c;

if ( colour(graph, m, color, v + 1)== 1)

return 1;

color[v] = 0; }

return 0;

void graphColoring(int graph[V][V], int m) {

int color[V];

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

color[i] = 0;
if (colour(graph, m, color, 0)== 0) {

printf("Yes its %d colorable\n",m);

return 1;

int main() {

int e;

printf("Enter no. of vertices and edges\n");

scanf("%d %d",&V,&e);

int graph[V][V];

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

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

graph[i][j]=0;

while(e--){

int u,v;

printf("Enter edge details\n");

scanf("%d %d",&u,&v);

graph[u][v]=1;

graph[v][u]=1;

int m;

printf("Number of colors\n");

scanf("%d",&m);

graphColoring(graph, m);

return 0;

}
Output:

You might also like