Must answer output screenshot, editable code
Code this in
java.
public static int [] graphColoring(int n, int [][] W)
The method returns an array with cells 1 through n giving an k-coloring of the graph, where k is the minimum number of colors needed to color the graph. Cell 0 of the array will contain the value −k.
It does this by calling a method that implements a backtracking algorithm with k=1,2,3, etc, until a valid k-coloring is found.
The method that implements the backtracking algorithm must return a boolean value: true if it finds a solution, and false if it doesn’t. If it does find a solution, it must stop looking for other solutions.
You will need to write the promising method in addition to the boolean graph coloring method.
You have also been given 4 test cases. The arrays that should be returned for these test cases are as follows:
[][] W1 = {
{},
{-1, 0, 1, 1},
{-1, 1, 0, 1},
{-1, 1, 1, 0}
};
Should return for W1: {-3, 1, 2, 3}
[][] W2 = {
{},
{-1, 0, 0, 1, 0},
{-1, 0, 0, 0, 1},
{-1, 1, 0, 0, 1},
{-1, 0, 1, 1, 0}
};
Should return for W2: {-2, 1, 2, 2, 1}
[][] W3 = {
{},
{-1, 0, 0, 1, 1, 1},
{-1, 0, 0, 1, 0, 0},
{-1, 1, 1, 0, 1, 1},
{-1, 1, 0, 1, 0, 1},
{-1, 1, 0, 1, 1, 0}
};
Should return for W3: {-4, 1, 1, 2, 3, 4}
[][] W4 = {
{},
{-1, 0, 1, 0, 1, 0, 1},
{-1, 1, 0, 1, 0, 1, 0},
{-1, 0, 1, 0, 0, 0, 1},
{-1, 1, 0, 0, 0, 1, 1},
{-1, 0, 1, 0, 1, 0, 0},
{-1, 1, 0, 1, 1, 0, 0}
};
Should return for W4: {-3, 1, 2, 1, 2, 1, 3}
public class GraphColoring {
public static void main(String [] args) {
}
public static int [] graphColor(int n, int [][] W) {
}
public static int [][] W1 = {
{},
{-1, 0, 1, 1},
{-1, 1, 0, 1},
{-1, 1, 1, 0}
};
public static int [][] W2 = {
{},
{-1, 0, 0, 1, 0},
{-1, 0, 0, 0, 1},
{-1, 1, 0, 0, 1},
{-1, 0, 1, 1, 0}
};
public static int [][] W3 = {
{},
{-1, 0, 0, 1, 1, 1},
{-1, 0, 0, 1, 0, 0},
{-1, 1, 1, 0, 1, 1},
{-1, 1, 0, 1, 0, 1},
{-1, 1, 0, 1, 1, 0}
};
public static int [][] W4 = {
{},
{-1, 0, 1, 0, 1, 0, 1},
{-1, 1, 0, 1, 0, 1, 0},
{-1, 0, 1, 0, 0, 0, 1},
{-1, 1, 0, 0, 0, 1, 1},
{-1, 0, 1, 0, 1, 0, 0},
{-1, 1, 0, 1, 1, 0, 0}
};
}