Question

Translate psuedo code for computing chromatic number of a grapgh to java code

1 //graph G, vertices n, vertices are numbered o,1-- //G i //colors are stored in arrayq //qlil has color of vertex i, initially all0 s stored in adjacency list or adjacency matrix p , returns chromatic number //colors G using mininum number of colors int color () for (i 1 to n) //if G can be colored using i colors starting at vertex 0 if (color (0, i)) chromatic number is i, return it //colors G using n colors starting at vertex v boolean color (v, m) if (v exceeds n-1) all vertices have been colored, success else for (i = 1 to m) assign color i to vertex v check whether colors of v and its neighbors conflict if (colors do not conflict) color the rest of G using m colors starting at vertex v+1, done by recursive call color (v+1, m) if (the rest of G can be colored) all vertices have been colored, success assign color 0 to vertex v and fail, this happens when none of the m colors can be assigned to vertex v //in color ) method, chromatic numbers can be tried in ascending order // (İ-: 1 to n) or descending order (i-n to 1), and both orders can b //used to find a range of possible values of the chromatic number

Answer 1

// A Java program to implement greedy algorithm for graph coloring import java.io.*; import java.util.*; import java.util.LinkedList;    // This class represents an undirected graph using adjacency list class Graph {     private int V;   // No. of vertices     private LinkedList<Integer> adj[]; //Adjacency List        //Constructor     Graph(int v)     {         V = v;         adj = new LinkedList[v];         for (int i=0; i<v; ++i)             adj[i] = new LinkedList();     }        //Function to add an edge into the graph     void addEdge(int v,int w)     {         adj[v].add(w);         adj[w].add(v); //Graph is undirected     }        // Assigns colors (starting from 0) to all vertices and     // prints the assignment of colors     void greedyColoring()     {         int result[] = new int[V];            // Initialize all vertices as unassigned         Arrays.fill(result, -1);            // Assign the first color to first vertex         result[0] = 0;            // A temporary array to store the available colors. False         // value of available[cr] would mean that the color cr is         // assigned to one of its adjacent vertices         boolean available[] = new boolean[V];                    // Initially, all colors are available         Arrays.fill(available, true);            // Assign colors to remaining V-1 vertices         for (int u = 1; u < V; u++)         {             // Process all adjacent vertices and flag their colors             // as unavailable             Iterator<Integer> it = adj[u].iterator() ;             while (it.hasNext())             {                 int i = it.next();                 if (result[i] != -1)                     available[result[i]] = false;             }                // Find the first available color             int cr;             for (cr = 0; cr < V; cr++){                 if (available[cr])                     break;             }                result[u] = cr; // Assign the found color                // Reset the values back to true for the next iteration             Arrays.fill(available, true);         }            // print the result         for (int u = 0; u < V; u++)             System.out.println("Vertex " + u + " ---> Color "                                 + result[u]);     }        // Driver method     public static void main(String args[])     {         Graph g1 = new Graph(5);         g1.addEdge(0, 1);         g1.addEdge(0, 2);         g1.addEdge(1, 2);         g1.addEdge(1, 3);         g1.addEdge(2, 3);         g1.addEdge(3, 4);         System.out.println("Coloring of graph 1");         g1.greedyColoring();            System.out.println();         Graph g2 = new Graph(5);         g2.addEdge(0, 1);         g2.addEdge(0, 2);         g2.addEdge(1, 2);         g2.addEdge(1, 4);         g2.addEdge(2, 4);         g2.addEdge(4, 3);         System.out.println("Coloring of graph 2 ");         g2.greedyColoring();     } } Output:--Coloring of graph 1 Vertex 0 ---> Color 0 Vertex 1 ---> Color 1 Vertex 2 ---> Color 2 Vertex 3 ---> Color 0 Vertex 4 ---> Color 1 Output:--Coloring of graph 2 Vertex 0 ---> Color 0 Vertex 1 ---> Color 1 Vertex 2 ---> Color 2 Vertex 3 ---> Color 0 Vertex 4 ---> Color 3