Algorithms/graphColoring.java at master · ravikiradoo/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

import java.util.*;

class Graph
{
   static  int V;
   static int graph[][];
   static int m;
   static int color[];
  public static void main(String args[])

   {

    Scanner scan=new Scanner(System.in);
     V=scan.nextInt();
     graph = new int[V][V];
     m=scan.nextInt();
    color=new int[V];

    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            graph[i][j]=scan.nextInt();
        }
    }
    if(GraphColoring(0)==true)
    {
        for(int i=0;i<V;i++)
        {
           System.out.println(color[i]);
        }
    }
    else
    {
        System.out.println("Coloring Not Possible");
    }

   }
  static boolean GraphColoring(int v)
   {
       if(v==V)
       return true;


       for(int c=1;c<=m;c++)
       {
           if(isSafe(v,c))
           {
               color[v]=c;

               if(GraphColoring(v+1))
               return true;

             color[v]=0;

           }
       }
       return false;
   }

   static boolean isSafe(int v,int c)
   {
       for(int i=0;i<V;i++)
       {
           if(graph[i][v]==1 && c==color[i])
           return false;

       }
       return true;
   }

}