[go: up one dir, main page]
Scribd
Upload
112 views3 pages

Graph Coloring

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
112 views3 pages

Graph Coloring

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
You are on page 1/ 3

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