Write a program to Coloring a Graph.

Name of the experiment:  Write a program to Coloring a Graph.

Algorithm:

1          Algorithm mColoring(k)

2          {

3                      repeat

4                      {

5                                  NextVAlue(k);

6                                  if (x[k]=0 then return;

7                                  if(k=n) then

8                                              write (x[1:n]);

9                                  else mColoring(k+1);

10                   }

11                   until (false);

12       }

Algorithm:

1          Algorithm NextValue(k)

2          {

3                      repeat

4                      {

5                                  x[k]:= (x[k]+1) mod  (m+1);

6                                  if (x[k]=0) then return;

7                                  for  j:= 1  to n  do

8                                  {

9                                              if ((G[k,j] ≠ 0)  and (x[k] = x[j]));

10                                           then break;

11                               }

12                               if (j= n+1) then return;

13                   }

14                   until (false);

15       }

Source code:

#include<stdio.h>

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

void next_color(int k)

{

int i,j;

x[k]=1; 

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

{

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

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

}

}

int main()

{

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

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

scanf("%d",&n); 

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

scanf("%d",&e); 

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

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

G[i][j]=0; 

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("Colors of vertices -->\n");

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

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

return 0;

}

Sample Input and Output:

Output:

Enter no. of vertices : 4

Colored vertices of Graph G

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