Implementation of Graph Coloring Algorithm in Java

Graph Coloring is a way of coloring the vertices of a undirected graph such that no two adjacent vertices share the same color.

import java.io.*;
class GraphColor
{
int g[][],n,m,e;
int x[];
void read() throws IOException
{
BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“How many vertices and edges..”);
n=Integer.parseInt(in.readLine());
g=new int[n+1][n+1];
x=new int[n+1];
e=Integer.parseInt(in.readLine());
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=0; for(int i=1;i<=e;i++) { System.out.println("Enter end vertices..."); int a=Integer.parseInt(in.readLine()); int b=Integer.parseInt(in.readLine()); g[a][b]=g[b][a]=1; } System.out.println("How many colors..."); m=Integer.parseInt(in.readLine()); } void mColoring(int k) { do { nextValue(k); if(x[k]==0) break; if (k==n) { for(int i=1;i<=k;i++) System.out.print(x[i]+" "); 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) break; for(j=1;j<=n;j++) { if(g[k][j]!=0&&x[j]==x[k]) break; } if(j==n+1) break; } while(true); } } class TestGraphColor { public static void main(String args[]) throws IOException { GraphColor ob=new GraphColor(); ob.read(); ob.mColoring(1); } } /* How many vertices and edges.. 6 8 Enter end vertices... 1 2 Enter end vertices... 1 3 Enter end vertices... 2 3 Enter end vertices... 2 4 Enter end vertices... 3 5 Enter end vertices... 4 5 Enter end vertices... 4 6 Enter end vertices... 5 6 How many colors... 3 1 2 3 1 2 3 1 2 3 3 1 2 1 2 3 3 2 1 1 3 2 1 3 2 1 3 2 2 1 3 1 3 2 2 3 1 2 1 3 2 1 3 2 1 3 3 1 2 2 1 3 3 2 1 2 3 1 1 2 3 2 3 1 1 3 2 2 3 1 2 3 1 3 1 2 2 1 3 3 1 2 2 3 1 3 1 2 3 1 2 3 2 1 1 2 3 3 2 1 1 3 2 3 2 1 3 2 1 Process Exit... */ [/java]

Leave a Reply

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