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);
}
void
nextvalue(int k)
{
int j;
do
{
x[k]=(x[k]+1)%(m+1);
if(x[k]==0) return;
for(j=1;j<=n;j++)
{
if((a[k][j]==1) && (x[k]==x[j]))
break;
}
if(j==n+1) return;
}while(true);
}
}
class Graphcoloring
{
public static void
main(String args[ ])throws IOException
{
gcoloring g=new
gcoloring();
g.read();
}
}
OUTPUT:
-------
Enter number of vertices in the graph
4
Enter 1 if there is an edge Otherwise 0
between 1 and 1
0
between 1 and 2
1
between 1 and 3
0
between 1 and 4
1
between 2 and 1
1
between 2 and 2
0
between 2 and 3
1
between 2 and 4
0
between 3 and 1
0
between 3 and 2
1
between 3 and 3
0
between 3 and 4
1
between 4 and 1
1
between 4 and 2
0
between 4 and 3
1
between 4 and 4
0
Given adjacency matrix is
0 1 0
1
1 0 1
0
0 1 0
1
1 0 1
0
All possible combinations for m = 2 are
1 2 1
2
2 1 2
1
All possible combinations for m = 3 are
1 2 1
2
1 2 1
3
1 2 3
2
1 3 1
2
1 3 1
3
1 3 2
3
2 1 2
1
2 1 2
3
2 1 3
1
2 3 1
3
2 3 2
1
2 3 2
3
3 1 2
1
3 1 3
1
3 1 3
2
3 2 1
2
3 2 3
1
3 2 3
2
RESULT
Thus the program for graph coloring using Java has been
implemented.
No comments:
Post a Comment