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[];
System.out.println("How many vertices and edges..");
g = new int[n + 1][n + 1];
x = new int[n + 1];
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...");
}

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.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...
*/
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.