Graph Coloring > Java Program

Analysis of Algorithm

Graph Coloring > Java Program

import java.util.*; 
class GraphColoring 
{  
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 GraphColoringExp 
{  
public static void main(String args[])  
{   
GraphColoring obj=new GraphColoring();   
System.out.println("Solutions :");   
obj.colorGraph(0);  
} 
}