AIM
To write the Java program for the
implementation of graph coloring
ALGORITHM
Step 1:
Start the program and define the function
Step 2:
Create a class coloring
Step
3:
Get the number of vertices in the graph
Step
4:
Enter one if there is an edge in the graph
Step
5:
And enter zero if there is no edge in the graph.
Step 6:
Get the adjacency matrix of the given values
Step 7:
Perform all possible combinations that are given
Step 8:
Display all the combination
Step 9:
End of the program
PROGRAM
GRAPH COLORING
USING BACKTRACKING
import java.io.*;
class gcoloring
{
int a[][]=new
int[10][10];
int x[]=new int[10];
int m, n;
void read()
{
DataInputStream in=new DataInputStream(System.in);
try
{
System.out.println("Enter number of vertices in the
graph");
n=Integer.parseInt(in.readLine());
System.out.println("Enter
1 if there is an edge Otherwise 0");
for(int
i=1;i<=n;i++)
for(int
j=1;j<=n;j++)
{
System.out.println("between "+i+" and "+j);
a[i][j]=Integer.parseInt(in.readLine());
}
}
catch(Exception e){}
System.out.println("Given adjacency matrix is ");
for(int
i=1;i<=n;i++)
{
for(int
j=1;j<=n;j++)
System.out.print(a[i][j]+"\t");
System.out.println();
}
for(int i=1;i<=n;i++)
x[i]=0;
for(int
i=2;i<n;i++)
{
m=i;
System.out.println("All possible combinations for m =
"+i+" are ");
mcoloring(1);
}
}
void
mcoloring(int k)
{
do
{
nextvalue(k);
if(x[k]==0)
break;
if(k==n)
{
for(int
i=1;i<=n;i++)
System.out.print(x[i]+"\t");
System.out.println();
}
else
mcoloring(k+1);
}while(true);
}
