{"id":26398,"date":"2017-10-26T21:58:02","date_gmt":"2017-10-26T16:28:02","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26398"},"modified":"2017-10-26T21:58:02","modified_gmt":"2017-10-26T16:28:02","slug":"c-programming-graph-coloring-set-2-greedy-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-graph-coloring-set-2-greedy-algorithm\/","title":{"rendered":"C programming &#8211; Graph Coloring | Set 2 (Greedy Algorithm)"},"content":{"rendered":"<p>We introduced <a href=\"http:\/\/www.geeksforgeeks.org\/graph-coloring-applications\/\" target=\"_blank\" rel=\"noopener noreferrer\">graph coloring and applications<\/a> in previous post. As discussed in the previous post, graph coloring is widely used. <span id=\"more-123945\"><\/span>Unfortunately, there is no efficient algorithm available for coloring a graph with minimum number of colors as the problem is a known <a href=\"http:\/\/www.geeksforgeeks.org\/np-completeness-set-1\/\" target=\"_blank\" rel=\"noopener noreferrer\">NP Complete problem<\/a>. There are approximate algorithms to solve the problem though. Following is the basic Greedy Algorithm to assign colors. It doesn\u2019t guarantee to use minimum colors, but it guarantees an upper bound on the number of colors. The basic algorithm never uses more than d+1 colors where d is the maximum degree of a vertex in the given graph.<\/p>\n<p><strong>Basic Greedy Coloring Algorithm:<\/strong><\/p>\n<pre><strong>1.<\/strong> Color first vertex with first color.\r\n<strong>2.<\/strong> Do following for remaining V-1 vertices.\r\n         <strong> a) <\/strong>Consider the currently picked vertex and color it with the \r\n             lowest numbered color that has not been used on any previously\r\n             colored vertices adjacent to it. If all previously used colors \r\n             appear on vertices adjacent to v, assign a new color to it.\r\n<strong>C++ program\r\n\/\/ A C++ program to implement greedy algorithm for graph coloring\r\n#include &lt;iostream&gt;\r\n#include &lt;list&gt;\r\nusing namespace std;\r\n \r\n\/\/ A class that represents an undirected graph\r\nclass Graph\r\n{\r\n int V; \/\/ No. of vertices\r\n list&lt;int&gt; *adj; \/\/ A dynamic array of adjacency lists\r\npublic:\r\n \/\/ Constructor and destructor\r\n Graph(int V) { this-&gt;V = V; adj = new list&lt;int&gt;[V]; }\r\n ~Graph() { delete [] adj; }\r\n \r\n \/\/ function to add an edge to graph\r\n void addEdge(int v, int w);\r\n \r\n \/\/ Prints greedy coloring of the vertices\r\n void greedyColoring();\r\n};\r\n \r\nvoid Graph::addEdge(int v, int w)\r\n{\r\n adj[v].push_back(w);\r\n adj[w].push_back(v); \/\/ Note: the graph is undirected\r\n}\r\n \r\n\/\/ Assigns colors (starting from 0) to all vertices and prints\r\n\/\/ the assignment of colors\r\nvoid Graph::greedyColoring()\r\n{\r\n int result[V];\r\n \r\n \/\/ Assign the first color to first vertex\r\n result[0] = 0;\r\n \r\n \/\/ Initialize remaining V-1 vertices as unassigned\r\n for (int u = 1; u &lt; V; u++)\r\n result[u] = -1; \/\/ no color is assigned to u\r\n \r\n \/\/ A temporary array to store the available colors. True\r\n \/\/ value of available[cr] would mean that the color cr is\r\n \/\/ assigned to one of its adjacent vertices\r\n bool available[V];\r\n for (int cr = 0; cr &lt; V; cr++)\r\n available[cr] = false;\r\n \r\n \/\/ Assign colors to remaining V-1 vertices\r\n for (int u = 1; u &lt; V; u++)\r\n {\r\n \/\/ Process all adjacent vertices and flag their colors\r\n \/\/ as unavailable\r\n list&lt;int&gt;::iterator i;\r\n for (i = adj[u].begin(); i != adj[u].end(); ++i)\r\n if (result[*i] != -1)\r\n available[result[*i]] = true;\r\n \r\n \/\/ Find the first available color\r\n int cr;\r\n for (cr = 0; cr &lt; V; cr++)\r\n if (available[cr] == false)\r\n break;\r\n \r\n result[u] = cr; \/\/ Assign the found color\r\n \r\n \/\/ Reset the values back to false for the next iteration\r\n for (i = adj[u].begin(); i != adj[u].end(); ++i)\r\n if (result[*i] != -1)\r\n available[result[*i]] = false;\r\n }\r\n \r\n \/\/ print the result\r\n for (int u = 0; u &lt; V; u++)\r\n cout &lt;&lt; \"Vertex \" &lt;&lt; u &lt;&lt; \" ---&gt; Color \"\r\n &lt;&lt; result[u] &lt;&lt; endl;\r\n}\r\n \r\n\/\/ Driver program to test above function\r\nint main()\r\n{\r\n Graph g1(5);\r\n g1.addEdge(0, 1);\r\n g1.addEdge(0, 2);\r\n g1.addEdge(1, 2);\r\n g1.addEdge(1, 3);\r\n g1.addEdge(2, 3);\r\n g1.addEdge(3, 4);\r\n cout &lt;&lt; \"Coloring of graph 1 \\n\";\r\n g1.greedyColoring();\r\n \r\n Graph g2(5);\r\n g2.addEdge(0, 1);\r\n g2.addEdge(0, 2);\r\n g2.addEdge(1, 2);\r\n g2.addEdge(1, 4);\r\n g2.addEdge(2, 4);\r\n g2.addEdge(4, 3);\r\n cout &lt;&lt; \"\\nColoring of graph 2 \\n\";\r\n g2.greedyColoring();\r\n \r\n return 0;\r\n}\r\nOutput:<\/strong><\/pre>\n<pre>Coloring of graph 1\r\nVertex 0 ---&gt;  Color 0\r\nVertex 1 ---&gt;  Color 1\r\nVertex 2 ---&gt;  Color 2\r\nVertex 3 ---&gt;  Color 0\r\nVertex 4 ---&gt;  Color 1\r\n\r\nColoring of graph 2\r\nVertex 0 ---&gt;  Color 0\r\nVertex 1 ---&gt;  Color 1\r\nVertex 2 ---&gt;  Color 2\r\nVertex 3 ---&gt;  Color 0\r\nVertex 4 ---&gt;  Color 3<\/pre>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>C programming &#8211; Graph Coloring | Set 2 (Greedy Algorithm) &#8211; Graph Algorithms &#8211; It doesn\u2019t guarantee to use minimum colors, but it guarantees an upper bound <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,69866,1,73906,78521],"tags":[74796,78573,78690,78689,74812,78691,78687,78688],"class_list":["post-26398","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-graph-algorithms","category-hard-problems","tag-graph-coloring-algorithm-using-backtracking","tag-graph-coloring-algorithm-with-example","tag-graph-coloring-applications","tag-graph-coloring-code-in-c","tag-graph-coloring-example","tag-graph-coloring-greedy-algorithm","tag-graph-coloring-program-in-c","tag-graph-colouring-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26398","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26398"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26398\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26398"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26398"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26398"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}