Java is the required programming language To address the impending STEM shortage

Question

Java is the required programming language

To address the impending STEM shortage early on, your local elementary school decided to teach graph theory to its kindergarten students! To tap into their age-specific skills, the students are asked to color the vertices ofa graph with colors of their own choosing. There is one constraint, however: they cannot use the same color for two vertices if those vertices are connected by an edge Furthermore, they are asked to use as few different colors as possible. The illustration shows a few examples of student work. t- » A 3 2 2 3 There is one problem, as you can imagine: there is no money to train teachers to grade these students' submissions! Thus, your task is to write a program that computes the sample solutions for the graphs given on each work sheet! Input The input consists of a description of a single graph. The first line contains a number N (2

Explanation / Answer

/* Graph Coloring in java*/
import java.io.*;
import java.util.*;
import java.util.LinkedList;

/* This class represents an undirected graph */
class Graph_Colour
{
private int Vertices; // No. of vertices
private LinkedList<Integer> adj[]; //To contin adjacency List

//Constructor to intialize the
Graph_Colour(int v)
{
Vertices = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}

/* Function to add an edge */
void addEdge(int v,int w)
{
adj[v].add(w);
adj[w].add(v);
}

/* Assigns colors to all vertices */
void Coloring()
{
int result[] = new int[Vertices];

Arrays.fill(result, -1);

result[0] = 0;

/* A temporary array to store the available colors */
boolean available_colours[] = new boolean[Vertices];

Arrays.fill(available_colours, true); /* Starting-> all the colors are available */

for (int u = 1; u < Vertices; u++)
{
/* Go through all adjacent vertices and flag their colors */
Iterator<Integer> it = adj[u].iterator() ;
while (it.hasNext())
{
int i = it.next();
if (result[i] != -1)
available_colours[result[i]] = false;
}

// Find the first available color
int cr;
for (cr = 0; cr < Vertices; cr++){
if (available_colours[cr])
break;
}

result[u] = cr; /* Assign colour */

/* Reset the values be to true for the next iteration */
Arrays.fill(available_colours, true);
}

  
int min=-1; /* Minimum number of colours required */
for (int u = 0; u < Vertices; u++)
if(min<result[u])
min=result[u]; /* maximum of the result array is having minimum number of colours */
min=min+1;
System.out.println(min);
}

public static void main(String args[])
{
Graph_Colour g = new Graph_Colour(4);
g.addEdge(0, 1);
g.addEdge(0, 2); /* Considering the given sample as a test case*/
g.addEdge(1, 2);
g.addEdge(2, 3);
System.out.println("Minimum no. of colors required to colour graph");
g.Coloring();
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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