![\"Backtracking](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Backtracking-Set-5-m-Coloring-Problem.png\"){kind=tracking}
<\/p>\nGiven an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.<\/p>\n
Input:
\n1) A 2D array graph[V][V] where V is the number of vertices in graph and graph[V][V] is adjacency matrix representation of the graph. A value graph[i][j] is 1 if there is a direct edge from i to j, otherwise graph[i][j] is 0.
\n2) An integer m which is maximum number of colors that can be used.<\/p>\n
Output:
\nAn array color[V] that should have numbers from 1 to m. color[i] should represent the color assigned to the ith vertex. The code should also return false if the graph cannot be colored with m colors.<\/p>\n
Following is an example graph (from Wiki page ) that can be colored with 3 colors.<\/p>\n
<\/p>\n
Naive Algorithm<\/strong> There will be V^m configurations of colors.<\/p>\n[ad type=\u201dbanner\u201d]\n Backtracking Algorithm<\/strong> Implementation of Backtracking solution<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%20%0A%2F%2F%20Number%20of%20vertices%20in%20the%20graph%0A%23define%20V%204%0A%20%0Avoid%20printSolution(int%20color%5B%5D)%3B%0A%20%0A%2F*%20A%20utility%20function%20to%20check%20if%20the%20current%20color%20assignment%0A%20%20%20is%20safe%20for%20vertex%20v%20*%2F%0Abool%20isSafe%20(int%20v%2C%20bool%20graph%5BV%5D%5BV%5D%2C%20int%20color%5B%5D%2C%20int%20c)%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(graph%5Bv%5D%5Bi%5D%20%26%26%20c%20%3D%3D%20color%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20return%20true%3B%0A%7D%0A%20%0A%2F*%20A%20recursive%20utility%20function%20to%20solve%20m%20coloring%20problem%20*%2F%0Abool%20graphColoringUtil(bool%20graph%5BV%5D%5BV%5D%2C%20int%20m%2C%20int%20color%5B%5D%2C%20int%20v)%0A%7B%0A%20%20%20%20%2F*%20base%20case%3A%20If%20all%20vertices%20are%20assigned%20a%20color%20then%0A%20%20%20%20%20%20%20return%20true%20*%2F%0A%20%20%20%20if%20(v%20%3D%3D%20V)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%2F*%20Consider%20this%20vertex%20v%20and%20try%20different%20colors%20*%2F%0A%20%20%20%20for%20(int%20c%20%3D%201%3B%20c%20%3C%3D%20m%3B%20c%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Check%20if%20assignment%20of%20color%20c%20to%20v%20is%20fine*%2F%0A%20%20%20%20%20%20%20%20if%20(isSafe(v%2C%20graph%2C%20color%2C%20c))%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20color%5Bv%5D%20%3D%20c%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F*%20recur%20to%20assign%20colors%20to%20rest%20of%20the%20vertices%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20if%20(graphColoringUtil%20(graph%2C%20m%2C%20color%2C%20v%2B1)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20assigning%20color%20c%20doesn\u2019t%20lead%20to%20a%20solution%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20then%20remove%20it%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20color%5Bv%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20If%20no%20color%20can%20be%20assigned%20to%20this%20vertex%20then%20return%20false%20*%2F%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F*%20This%20function%20solves%20the%20m%20Coloring%20problem%20using%20Backtracking.%0A%20%20It%20mainly%20uses%20graphColoringUtil()%20to%20solve%20the%20problem.%20It%20returns%0A%20%20false%20if%20the%20m%20colors%20cannot%20be%20assigned%2C%20otherwise%20return%20true%20and%0A%20%20prints%20assignments%20of%20colors%20to%20all%20vertices.%20Please%20note%20that%20there%0A%20%20may%20be%20more%20than%20one%20solutions%2C%20this%20function%20prints%20one%20of%20the%0A%20%20feasible%20solutions.*%2F%0Abool%20graphColoring(bool%20graph%5BV%5D%5BV%5D%2C%20int%20m)%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20all%20color%20values%20as%200.%20This%20initialization%20is%20needed%0A%20%20%20%20%2F%2F%20correct%20functioning%20of%20isSafe()%0A%20%20%20%20int%20*color%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20color%5Bi%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Call%20graphColoringUtil()%20for%20vertex%200%0A%20%20%20%20if%20(graphColoringUtil(graph%2C%20m%2C%20color%2C%200)%20%3D%3D%20false)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20printf(%22Solution%20does%20not%20exist%22)%3B%0A%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20the%20solution%0A%20%20%20%20printSolution(color)%3B%0A%20%20%20%20return%20true%3B%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20print%20solution%20*%2F%0Avoid%20printSolution(int%20color%5B%5D)%0A%7B%0A%20%20%20%20printf(%22Solution%20Exists%3A%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%20Following%20are%20the%20assigned%20colors%20%5Cn%22)%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20printf(%22%20%25d%20%22%2C%20color%5Bi%5D)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Create%20following%20graph%20and%20test%20whether%20it%20is%203%20colorable%0A%20%20%20%20%20%20(3)\u2014(2)%0A%20%20%20%20%20%20%20%7C%20%20%20%2F%20%7C%0A%20%20%20%20%20%20%20%7C%20%20%2F%20%20%7C%0A%20%20%20%20%20%20%20%7C%20%2F%20%20%20%7C%0A%20%20%20%20%20%20(0)\u2014(1)%0A%20%20%20%20*%2F%0A%20%20%20%20bool%20graph%5BV%5D%5BV%5D%20%3D%20%7B%7B0%2C%201%2C%201%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%7B1%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%7B1%2C%201%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%7B1%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%7D%3B%0A%20%20%20%20int%20m%20%3D%203%3B%20%2F%2F%20Number%20of%20colors%0A%20%20%20%20graphColoring%20(graph%2C%20m)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n Output:<\/strong><\/p>\n Backtracking Set 5 (m Coloring Problem)-Backtracking-Given an undirected graph and a number m, determine if the graph can be colored with at most m colors .<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73907],"tags":[74805,74485,74484,74498,74801,74791,74799,74823,73908,74160,74164,74493,74162,74810,74816,74819,74811,74803,74802,74822,74793,74804,74806,74792,74795,74488,74797,74491,74800,74807,70598,74815,74798,74796,74812,74817,74163,74818,74821,74813,74814,74809,74501,74509,74820,74496,74614,74794,74808],"class_list":["post-25687","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-backtracking-algorithm","tag-2-color","tag-4-queen-problem-using-backtracking","tag-4-queens-problem-using-backtracking-algorithm","tag-8-queen-problem-using-backtracking","tag-aakash-assignment-solutions","tag-aakash-solutions","tag-aakash-target-solutions","tag-algorithm-graph","tag-backtracking-algorithm","tag-backtracking-algorithm-example","tag-backtracking-algorithm-pdf","tag-backtracking-in-daa","tag-backtracking-problems","tag-ccc-color","tag-chromatic-number","tag-chromatic-number-of-a-graph","tag-color-definition","tag-color-numbers","tag-color-set","tag-color-tree","tag-coloring","tag-colour-numbers","tag-colour-tree","tag-colouring-in","tag-conjuring2","tag-constraint-satisfaction-problem","tag-constraint-satisfaction-problem-in-artificial-intelligence","tag-cryptarithmetic-problem-solved-examples","tag-face-colour","tag-facecolor","tag-graph-algorithms","tag-graph-coloring","tag-graph-coloring-algorithm","tag-graph-coloring-algorithm-using-backtracking","tag-graph-coloring-example","tag-graph-coloring-problem","tag-graph-coloring-using-backtracking","tag-graph-colouring","tag-graph-problems","tag-hamiltonian-cycle-algorithm-using-backtracking","tag-knapsack-problem-using-backtracking","tag-m-coloring-problem","tag-n-queen-problem-using-backtracking","tag-n-queens-problem-using-backtracking","tag-state-space-tree","tag-sum-of-subset-problem-using-backtracking","tag-sum-of-subsets-using-backtracking","tag-types-of-colours","tag-vertex-color"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25687","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=25687"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25687\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25687"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25687"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25687"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nGenerate all possible configurations of colors and print a configuration that satisfies the given constraints.<\/p>\nwhile there are untried conflagrations\r\n{\r\n generate the next configuration\r\n if no adjacent vertices are colored with same color\r\n {\r\n print this configuration;\r\n }\r\n}\r\n<\/pre>\n
\nThe idea is to assign colors one by one to different vertices, starting from the vertex 0. Before assigning a color, we check for safety by considering already assigned colors to the adjacent vertices. If we find a color assignment which is safe, we mark the color assignment as part of solution. If we do not a find color due to clashes then we backtrack and return false.<\/p>\nSolution Exists: Following are the assigned colors\r\n 1 2 3 2<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"