graph coloring algorithm program in java

import java.util.*;
class Graph_Coloring
{
private int adj[][],x[],m,n;
public GraphColoring()
{
Scanner src = new Scanner(System.in);
System.out.println("Enter the number of nodes");
n=src.nextInt();
x=new int[n];
for (int i=0;i<n; i++)
x[i]=0;
adj=new int[n][n];
System.out.println("Enter the adjacency matrix");
for (int i=0;i<n; i++)
for (int j=0; j<n; j++)
adj[i][j]=src.nextInt();
System.out.println("Enter number of colors");
m=src.nextInt();
}

public void nextValue (int k)
{
int i;
while(true)
{
x[k]=(x[k]+1)%(m+1);
if (x[k]==0)
return;
for (i=0; i<k; i++)
if (adj[i][k]==1 && x[i]==x[k])
break;
if (i==k) // legal color is found
break;
}
}

public void colorGraph(int k)
{
while(true)
{
nextValue(k);
if (x[k]==0)
return;
if (k==n-1)
{
for (int i=0; i<n; i++)
System.out.print(x[i]+" ");
System.out.println("\n");
}
else colorGraph(k+1);
}
}
}
class Graph_ColoringExp
{
public static void main(String args[])
{
Graph_Coloring obj=new Graph_Coloring();
System.out.println("Solutions :");
obj.colorGraph(0);

}
}

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *