JAVA A graph coloring assigns a color to every vertex in a graph, with the restr

Question

JAVA

A graph coloring assigns a color to every vertex in a graph, with the restriction that vertices with the same color cannot be adjacent. A graph is said to be k-colorable if it can be colored in k or fewer colors. Add a method to DirectedGraph that will return true for instances that are 2-Colorable. The method should have the following signature: public boolean is2Colorable() What to Submit: DirectedGraph.java. (It is fine to write a single DirectedGraph.java with isConnected(), isAcyclic(), and is2Colorable(). But be sure to submit the file in both places on the insight home page: Both the last regular assignment, and the extra credit assignment.)

Explanation / Answer

Java program for solution Coloring

public class mColoringProblem {
final int V = 4;
int color[];

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

boolean graphColoringUtil(int graph[][], int m,
int color[], int v)
{
/* base case: If all vertices are assigned
a color then return true */
if (v == V)
return true;

/* Consider this vertex v and try different
colors */
for (int c = 1; c <= m; c++)
{
/* Check if assignment of color c to v
is fine*/
if (isSafe(v, graph, color, c))
{
color[v] = c;

/* recur to assign colors to rest
of the vertices */
if (graphColoringUtil(graph, m,
color, v + 1))
return true;

/* If assigning color c doesn't lead
to a solution then remove it */
color[v] = 0;
}
}

/* If no color can be assigned to this vertex
then return false */
return false;
}

  
boolean graphColoring(int graph[][], int m)
{
color = new int[V];
for (int i = 0; i < V; i++)
color[i] = 0;

// Call graphColoringUtil() for vertex 0
if (!graphColoringUtil(graph, m, color, 0))
{
System.out.println("Solution does not exist");
return false;
}

// Print the solution
printSolution(color);
return true;
}

/* A utility function to print solution */
void printSolution(int color[])
{
System.out.println("Solution Exists: Following" +
" are the assigned colors");
for (int i = 0; i < V; i++)
System.out.print(" " + color[i] + " ");
System.out.println();
}

// driver program to test above function
public static void main(String args[])
{
mColoringProblem Coloring = new mColoringProblem();
  
int graph[][] = {{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0},
};
int m = 3; // Number of colors
Coloring.graphColoring(graph, m);
}
}

thank you

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.