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?

ReplyDeleteI 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 :)

ReplyDelete