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

Leave a Reply

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