{"id":3585,"date":"2023-10-31T13:44:49","date_gmt":"2023-10-31T08:14:49","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3585"},"modified":"2023-10-31T13:44:50","modified_gmt":"2023-10-31T08:14:50","slug":"graph-coloring-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/graph-coloring-problem\/","title":{"rendered":"Graph Coloring Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-brute-force\">Approach 1: Brute Force<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#approach-2-backtracking\">Approach 2: Backtracking<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#frequently-asked-questions-faqs\">Frequently Asked Questions (FAQs)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-chromatic-number\">Q.1: What is the Chromatic Number<\/a><\/li><li><a href=\"#q2-what-does-the-backtracking-approach-have-the-same-time-complexity-as-the-brute-force-approach\">Q.2: What does the backtracking approach have the same time complexity as the brute force approach?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p><strong>Graph colouring<\/strong> problem involves assigning colours to certain elements of a graph subject to certain restrictions and constraints. In other words, the process of assigning colours to the vertices such that no two adjacent vertexes have the same colour is called Graph Colouring.<\/p>\n\n\n\n<p>This is also known as <strong>vertex colouring<\/strong>.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3768 pk-lazyload\"  width=\"569\"  height=\"376\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 569px) 100vw, 569px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-1024x677.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-1024x677.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-300x198.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-768x508.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-380x251.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-550x364.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-800x529.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3.png 1105w\" ><\/figure><\/div>\n\n\n\n<p><strong>Chromatic Number: <\/strong>&nbsp;The smallest number of colours needed to colour a graph G is called its chromatic number.<\/p>\n\n\n\n<p>For example, in the above image, vertices can be coloured using a minimum of 2 colours.<\/p>\n\n\n\n<p>Hence the <strong>chromatic number<\/strong> of the graph is 2.&nbsp;<\/p>\n\n\n\n<p>Further examples for a more clear understanding:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"643\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3769 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 643px) 100vw, 643px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-643x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-643x1024.png 643w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-188x300.png 188w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-768x1223.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-964x1536.png 964w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-1286x2048.png 1286w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-380x605.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-550x876.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-800x1274.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9-1160x1848.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-9.png 1354w\" ><\/figure>\n\n\n\n<p><strong>Applications of Graph Colouring<\/strong>:<\/p>\n\n\n\n<ul><li>Map Coloring<\/li><li>Scheduling the tasks<\/li><li>Preparing Time Table<\/li><li>Assignment<\/li><li>Conflict Resolution<\/li><li>Sudoku<\/li><\/ul>\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<ul><li>The simplest approach to solve this problem would be to generate all possible combinations (or configurations) of colours.<\/li><li>After generating a configuration, check if the adjacent vertices have the same colour or not. If the conditions are met, add the combination to the result and break the loop.<\/li><li>Since each node can be coloured by using any of the <strong>M<\/strong> colours, the total number of possible colour configurations are mV. The complexity is exponential which is very huge.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool isSafeToColor(vector &lt; vector &lt; int >> &amp; graph, vector &lt; int > color) {\n  for (int i = 0; i &lt; V; i++)\n    for (int j = i + 1; j &lt; V; j++)\n      if (graph[i][j] == 1 &amp;&amp; color[j] == color[i])\n        return false;\n  return true;\n}\n \nvoid printColorArray(vector &lt; int > color) {\n  cout &lt;&lt; (\"Solution colors are: \") &lt;&lt; endl;\n  for (int i = 0; i &lt; color.size(); i++) {\n    cout &lt;&lt; (color[i]);\n  }\n}\nbool graphColoring(vector &lt; vector &lt; int >> &amp; graph, int m, int i, vector &lt; int > color) {\n  if (i == V) {\n    if (isSafeToColor(graph, color)) {\n      printColorArray(color);\n      return true;\n    }\n    return false;\n  }\n  for (int j = 1; j &lt;= m; j++) {\n    color[i] = j;\n    if (graphColoring(graph, m, i + 1, color))\n      return true;\n \n    color[i] = 0;\n  }\n \n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">private static boolean isSafeToColor(int[][] graph, int[] color) {\n  for (int i = 0; i &lt; V; i++)\n    for (int j = i + 1; j &lt; V; j++)\n      if (graph[i][j] == 1 &amp;&amp; color[j] == color[i])\n        return false;\n  return true;\n}\n \nprivate static void printColorArray(int[] color) {\n  System.out.println(\"Solution colors are: \")\n  for (int i = 0; i &lt; color.length; i++) {\n    System.out.println(color[i]);\n  }\n}\nprivate static boolean graphColoring(int[][] graph, int m, int i, int[] color) {\n  if (i == V) {\n    if (isSafeToColor(graph, color)) {\n      printColorArray(color);\n      return true;\n    }\n    return false;\n  }\n  for (int j = 1; j &lt;= m; j++) {\n    color[i] = j;\n    if (graphColoring(graph, m, i + 1, color))\n      return true;\n \n    color[i] = 0;\n  }\n \n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def isSafeToColor(graph, color):\n    for i in range(V):\n        for j in range(i + 1, V):\n            if graph[i][j] == 1 and color[j] == color[i]:\n                return False\n    return True\n \n \ndef printColorArray(color):\n    print(\"Solution colors are: \")\n    for i in range(len(color)):\n        print(color[i], end=\" \")\n \n \ndef graphColoring(graph, m, i, color):\n    if i == V:\n        if isSafeToColor(graph, color):\n            printColorArray(color)\n            return True\n        return False\n \n    for j in range(1, m + 1):\n        color[i] = j\n        if graphColoring(graph, m, i + 1, color):\n            return True\n \n        color[i] = 0\n \n    return false<\/pre>\n\n\n\n<ul><li><strong>Time Complexity: <\/strong>O(M^V), where M is the total colours needed and V is the total vertices<\/li><li><strong>Space Complexity:<\/strong> O(V), as extra space is used for colouring vertices.<\/li><\/ul>\n\n\n\n<h2 id=\"approach-2-backtracking\">Approach 2: Backtracking<\/h2>\n\n\n\n<p>In the previous approach, trying and checking every possible combination was tedious and had an exponential time complexity.<br>Some of the permutation calculations were unnecessary but were calculated again and again. Therefore, the idea is to use a <strong>backtracking<\/strong> approach to solve the problem.<strong><br><br><\/strong>In this approach, the idea is to color a vertex and while coloring any adjacent vertex, choose a different color. Similarly, color every possible vertex following the restrictions, till any further vertex is left coloring. In any case, if all adjacent vertices for a given vertex are colored, then backtrack and change color.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"951\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3770 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 951px) 100vw, 951px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-951x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-951x1024.png 951w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-279x300.png 279w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-768x827.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-380x409.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-550x592.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-800x861.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11-1160x1249.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-11.png 1354w\" ><\/figure>\n\n\n\n<p>If after coloring, if we return back to the same vertex that was started with and all colors are used, then more colors are needed. Hence, return <strong>False<\/strong>.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Consider a color and check if it is valid i.e. from the given vertex check whether its adjacent vertices have been coloured with the same color.<\/li><li>If true, pick a different colour, else continue colouring the vertices.<\/li><li>If no other color is left un-used, then backtrack.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class InterviewBit {\n  public:\n    int V = 4;\n \n  bool isSafeToColor(int v, vector &lt; vector &lt; int >> &amp; graphMatrix, vector &lt; int > color, int c) {\n    for (int i = 0; i &lt; V; i++)\n      if (graphMatrix[v][i] == 1 &amp;&amp; c == color[i])\n        return false;\n    return true;\n  }\n \n  bool graphColorUtil(vector &lt; vector &lt; int >> &amp; graphMatrix, int m, vector &lt; int > color, int v) {\n    if (v == V)\n      return true;\n \n    for (int i = 1; i &lt;= m; i++) {\n      if (isSafeToColor(v, graphMatrix, color, i)) {\n        color[v] = i;\n        if (graphColorUtil(graphMatrix, m, color, v + 1))\n          return true;\n        color[v] = 0;\n      }\n    }\n    return false;\n  }\n \n  void printColoringSolution(int color[]) {\n    cout &lt;&lt; (\"Color schema for vertices are: \") &lt;&lt; endl;\n    for (int i = 0; i &lt; V; i++)\n      cout &lt;&lt; (color[i]) &lt;&lt; endl;\n  }\n  bool graphColoring(vector &lt; vector &lt; int >> &amp; graphMatrix, int m) {\n    vector &lt; int > color(V, 0);\n \n    if (!graphColorUtil(graphMatrix, m, color, 0)) {\n      cout &lt;&lt; \"Color schema not possible\" &lt;&lt; endl;\n      return false;\n    }\n \n    printColoringSolution(color);\n    return true;\n  }<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public class InterviewBit {\n        final int V = 4;\n        int[] color;\n        \n        boolean isSafeToColor(int v, int[][] graphMatrix, int[] color, int c)\n        {\n            for (int i = 0; i &lt; V; i++)\n                if (graphMatrix[v][i] == 1 &amp;&amp; c == color[i])\n                    return false;\n            return true;\n        }\n \n        boolean graphColorUtil(int[][] graphMatrix, int m, int[] color, int v)\n        {\n            if (v == V)\n                return true;\n \n            for (int i = 1;i &lt;= m; i++) \n            {\n                if (isSafeToColor(v, graphMatrix, color, i))\n                {\n                    color[v] =i;\n                    if (graphColorUtil(graphMatrix, m, color, v + 1))\n                        return true;\n                    color[v] = 0;\n                }\n            }\n            return false;\n        }\n \n        void printColoringSolution(int color[])\n        {\n            System.out.println(\"Color schema for vertices are: \");\n            for (int i = 0; i &lt; V; i++)\n                System.out.println(color[i]);\n        }\n        boolean graphColoring(int[][] graphMatrix, int m)\n        {\n            color = new int[V];\n            Arrays.fill(color,0);\n \n            if (!graphColorUtil(graphMatrix, m, color, 0)) \n            {\n                System.out.println(\n                    \"Color schema not possible\");\n                return false;\n            }\n \n            printColoringSolution(color);\n            return true;\n        }<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class InterviewBit:\n    V = 4;\n        \n    def isSafeToColor(v, graphMatrix, color, c):\n        for i in range(V):\n            if graphMatrix[v][i] == 1 and c == color[i]:\n                return False;\n        return True;\n \n    def graphColorUtil(graphMatrix, m, color, v):\n        \n        if v == V:\n            return True;\n \n        for i in range(1, m + 1):\n            if isSafeToColor(v, graphMatrix, color, i):\n                color[v] =i;\n                if graphColorUtil(graphMatrix, m, color, v + 1):\n                    return True;\n                color[v] = 0;\n                \n        return false;\n \n    def printColoringSolution(color):\n        print(\"Color schema for vertices are: \")\n        for i in range(V):\n            print(color[i])\n    def graphColoring(graphMatrix, m):\n        \n        color = [0]*(V)\n \n        if !graphColorUtil(graphMatrix, m, color, 0):\n            print(\"Color schema not possible\")\n            return False;\n \n        printColoringSolution(color);\n        return True;<\/pre>\n\n\n\n<ul><li><strong>Time Complexity: <\/strong>O(M^V), in the worst case.<\/li><li><strong>Space Complexity:<\/strong> O(V), as extra space is used for colouring vertices.<\/li><\/ul>\n\n\n\n<h2 id=\"frequently-asked-questions-faqs\">Frequently Asked Questions (FAQs)<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-chromatic-number\"><span id=\"q-1-what-is-the-chromatic-number\">Q.1: What is the Chromatic Number<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> The smallest number of colours needed to colour a graph G is called its chromatic number.<\/p>\n\n\n\n<h3 id=\"q2-what-does-the-backtracking-approach-have-the-same-time-complexity-as-the-brute-force-approach\"><span id=\"q-2-what-does-the-backtracking-approach-have-the-same-time-complexity-as-the-brute-force-approach\">Q.2: What does the backtracking approach have the same time complexity as the brute force approach?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> The backtracking approach is also a type of brute force. It is just used to eliminate bad decisions while colouring the vertices.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Graph colouring problem involves assigning colours to certain elements of a graph subject to certain restrictions&hellip;\n","protected":false},"author":5,"featured_media":3771,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[457,554],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3585"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3585"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3585\/revisions"}],"predecessor-version":[{"id":25944,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3585\/revisions\/25944"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3771"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3585"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3585"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3585"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}