Today I am going to post a program in C that is used for solving the Graph Coloring problem.

--------------------------------------------------------------------------------------------------------------------------

NOTE : This code is written,compiled and run with GCC compiler under Linux environment Ubuntu12.04LTS Precise Pangolin.

__: In this problem, for any given graph G we will have to color each of the vertices in G in such a way that no two adjacent vertices get the same color and the least number of colors are used.__**What is Graph-Coloring**__: First take input number of vertices and edges in graph G. Then input all the indexes of adjacency matrix of G whose value is 1. Now we will try to color each of the vertex. A next_color(k) function takes in index of the kth vertex which is to be colored. First we assign color1 to the kth vertex.Then we check whether it is connected to any of previous (k-1) vertices using backtracking. If connected then assign a color x[i]+1 where x[i] is the color of ith vertex that is connected with kth vertex.__**How to solve the problem**--------------------------------------------------------------------------------------------------------------------------

**SOURCE CODE**
--------------------------------------------------------------------------------------------------------------------------

**#include<stdio.h>**

int G[50][50],x[50];//G:adjacency matrix,x:colors

int G[50][50],x[50];

**//coloring vertex with color1**

void next_color(int k){

int i,j;

x[k]=1;

void next_color(int k){

int i,j;

x[k]=1;

**//checking all k-1 vertices**

for(i=0;i<k;i++){

for(i=0;i<k;i++){

**-**backtracking

**/if connected and has same color**

if(G[i][k]!=0 && x[k]==x[i]) /

if(G[i][k]!=0 && x[k]==x[i]) /

**//assign higher color than x[i]**

x[k]=x[i]+1;

x[k]=x[i]+1;

}

}

}

}

**//total vertices**

int main(){

int n,e,i,j,k,l;

printf("Enter no. of vertices : ");

scanf("%d",&n);

int main(){

int n,e,i,j,k,l;

printf("Enter no. of vertices : ");

scanf("%d",&n);

**//total edges**

printf("Enter no. of edges : ");

scanf("%d",&e);

printf("Enter no. of edges : ");

scanf("%d",&e);

**//assign 0 to all index of adjacency matrix**

for(i=0;i<n;i++)

for(j=0;j<n;j++)

G[i][j]=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

G[i][j]=0;

**//coloring each vertex**

printf("Enter indexes where value is 1-->\n");

for(i=0;i<e;i++){

scanf("%d %d",&k,&l);

G[k][l]=1;

G[l][k]=1;

}

for(i=0;i<n;i++)

next_color(i);

printf("Enter indexes where value is 1-->\n");

for(i=0;i<e;i++){

scanf("%d %d",&k,&l);

G[k][l]=1;

G[l][k]=1;

}

for(i=0;i<n;i++)

next_color(i);

**//displaying color of each vertex**

printf("Colors of vertices -->\n");

for(i=0;i<n;i++)

printf("Colors of vertices -->\n");

for(i=0;i<n;i++)

printf("Vertex[%d] : %d\n",i+1,x[i]);

return 0;

}

printf("Vertex[%d] : %d\n",i+1,x[i]);

return 0;

}

NOTE : This code is written,compiled and run with GCC compiler under Linux environment Ubuntu12.04LTS Precise Pangolin.

--------------------------------------------------------------------------------------------------------------------------

**OUTPUT**
--------------------------------------------------------------------------------------------------------------------------

Enter no. of vertices : 4

Enter no. of edges : 5

Enter indexes where value is 1-->

0 1

1 2

1 3

2 3

3 0

Colors of vertices -->

Vertex[1] : 1

Vertex[2] : 2

Vertex[3] : 1

Vertex[4] : 3

--------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------------------------------------------------

Colored vertices of Graph G |

Enter indexes where value is 1-->

0 1

1 2

1 3

2 3

3 0

Colors of vertices -->

Vertex[1] : 1

Vertex[2] : 2

Vertex[3] : 1

Vertex[4] : 3

--------------------------------------------------------------------------------------------------------------------------

**RELATED POSTS**
To understand m-coloring i.e. to color a graph with all possible m colors (hence known as M-Way Coloring or m-coloring) visit :

Tanks For sharing This Info

ReplyDeletethnx for sharing...

ReplyDeleteplz post n-queens problem

hello, welch coloring algorithm with the exam schedule will do Powel How can I watch the way, can you help?

ReplyDeletepoda potta

Deleteni poda thendi

DeleteI think this is greedy coloring, not backtracking.

ReplyDeletethis is backtracking because of the checking of all previous adjacent nodes for a current node under processing;

Deletegood!!1

ReplyDeletethank you very very much :)

ReplyDeleteis it excuted and the color display for you ?

Deletefor me the run exit at

Colors of vertices -->

what exactly "Enter indexes where value is 1" mean? i cant get it.

ReplyDeleteit mean ender the 2 nodes which you want to connect

ReplyDeleteYou idiot !

ReplyDeleteDon't you know how to spell a word

dont mess with mee...otherwise..i'll f uhhh.....

ReplyDeleteFuck yourself you bloody fucker !!

ReplyDeleteDon't call me a fucker, You moron !

DeleteSTFU, You sucker.!

Deletego to hell man...!!!!

ReplyDeleteWhat is the time complexity of this program

ReplyDeletethis algorithm giving wrong answer

ReplyDeleteeg

vertices 5

edges 8

0 1

0 2

1 2

1 3

1 4

2 3

2 4

3 4

answer should be 4 but no. of colors showing 3

I AM WAITING FOR correction in the code.

This comment has been removed by the author.

Deletei am waiting for the reply

ReplyDelete#include

Deleteint mat[50][50]; // " mat " : est un matrice adjacent

char (*a[50])[10],(*clr[50])[10],(*tmp[50])[10]; // 'clr' , 'a' et 'tmp' : sont des tableaux de chaine des caracteres rempli des colores

void color(int k,int n) // la fontion 'color' va colorer touts les sommet de facont minimal

{

int i;

clr[k]=a[0]; // initialisation de tableau 'clr' avec la color rouge

for(i=0;i ");

scanf("%d",&l); // entrer l'indice ligne par l'utilisateur

mat[c][l]=1; // donne '1' pour les sommet qui sont adjacent

mat[l][c]=1; // donne '1' pour les sommet qui sont adjacent

}

for(i=0;i<=n;i++) // remplire le tableau 'tmp' 'n' colore

tmp[i]=a[i];

for(i=0;i<n;i++)

color(i,n); // l'appele de la fonction 'color' pour colorer chaque sommet

printf("\n colore des sommet est : \n\n");

for(i=0;i<n;i++)

printf(" sommet[%d] : %s\n",i,clr[i]); // afficher a l'ecran la colore de chaque sommet

for(i=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

if(clr[i]==clr[j])

{

for(k=j;k<n;k++)

{

clr[j]=clr[j+1];

j=j+1;

n=n-1;

}

}

}

}

printf("\n\n le nbr des sommet est : %d",n ); // affiche le nbre de colore utiliser

printf("\n\n\n\n\n");

return 0;

}