{"id":26267,"date":"2017-10-26T20:45:17","date_gmt":"2017-10-26T15:15:17","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26267"},"modified":"2017-10-26T20:45:17","modified_gmt":"2017-10-26T15:15:17","slug":"java-algorithm-check-whether-given-graph-bipartite-not","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-check-whether-given-graph-bipartite-not\/","title":{"rendered":"Java Algorithm &#8211; Check whether a given graph is Bipartite or not"},"content":{"rendered":"<p>A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. <span id=\"more-117119\"><\/span>In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.<\/p>\n<p>A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. Note that it is possible to color a cycle graph with even cycle using two colors. For example, see the following graph.<\/p>\n<p>It is not possible to color a cycle graph with odd cycle using two colors.<\/p>\n<p><strong><em>Algorithm to check if a graph is Bipartite:<\/em><\/strong><br \/>\nOne approach is to check whether the graph is 2-colorable or not using backtracking algorithm m coloring problem.<br \/>\nFollowing is a simple algorithm to find out whether a given graph is Birpartite or not using Breadth First Search (BFS).<br \/>\n1. Assign RED color to the source vertex (putting into set U).<br \/>\n2. Color all the neighbors with BLUE color (putting into set V).<br \/>\n3. Color all neighbor\u2019s neighbor with RED color (putting into set U).<br \/>\n4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.<br \/>\n5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite)<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Java Programming:<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20find%20out%20whether%20a%20given%20graph%20is%20Bipartite%20or%20not%0Aimport%20java.util.*%3B%0Aimport%20java.lang.*%3B%0Aimport%20java.io.*%3B%0A%20%0Aclass%20Bipartite%0A%7B%0A%20%20%20%20final%20static%20int%20V%20%3D%204%3B%20%2F%2F%20No.%20of%20Vertices%0A%20%0A%20%20%20%20%2F%2F%20This%20function%20returns%20true%20if%20graph%20G%5BV%5D%5BV%5D%20is%20Bipartite%2C%20else%20false%0A%20%20%20%20boolean%20isBipartite(int%20G%5B%5D%5B%5D%2Cint%20src)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20color%20array%20to%20store%20colors%20assigned%20to%20all%20veritces.%0A%20%20%20%20%20%20%20%20%2F%2F%20Vertex%20number%20is%20used%20as%20index%20in%20this%20array.%20The%20value%20\u2032-1\u2019%0A%20%20%20%20%20%20%20%20%2F%2F%20of%20%20colorArr%5Bi%5D%20is%20used%20to%20indicate%20that%20no%20color%20is%20assigned%0A%20%20%20%20%20%20%20%20%2F%2F%20to%20vertex%20\u2019i\u2019.%20%20The%20value%201%20is%20used%20to%20indicate%20first%20color%0A%20%20%20%20%20%20%20%20%2F%2F%20is%20assigned%20and%20value%200%20indicates%20second%20color%20is%20assigned.%0A%20%20%20%20%20%20%20%20int%20colorArr%5B%5D%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3CV%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20colorArr%5Bi%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Assign%20first%20color%20to%20source%0A%20%20%20%20%20%20%20%20colorArr%5Bsrc%5D%20%3D%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20queue%20(FIFO)%20of%20vertex%20numbers%20and%20enqueue%0A%20%20%20%20%20%20%20%20%2F%2F%20source%20vertex%20for%20BFS%20traversal%0A%20%20%20%20%20%20%20%20LinkedList%3CInteger%3Eq%20%3D%20new%20LinkedList%3CInteger%3E()%3B%0A%20%20%20%20%20%20%20%20q.add(src)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Run%20while%20there%20are%20vertices%20in%20queue%20(Similar%20to%20BFS)%0A%20%20%20%20%20%20%20%20while%20(q.size()%20!%3D%200)%0A%20%20%20%20%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Dequeue%20a%20vertex%20from%20queue%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20u%20%3D%20q.poll()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20all%20non-colored%20adjacent%20vertices%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20v%3D0%3B%20v%3CV%3B%20%2B%2Bv)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20An%20edge%20from%20u%20to%20v%20exists%20and%20destination%20v%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20not%20colored%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(G%5Bu%5D%5Bv%5D%3D%3D1%20%26%26%20colorArr%5Bv%5D%3D%3D-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Assign%20alternate%20color%20to%20this%20adjacent%20v%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20colorArr%5Bv%5D%20%3D%201-colorArr%5Bu%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q.add(v)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20An%20edge%20from%20u%20to%20v%20exists%20and%20destination%20v%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20colored%20with%20same%20color%20as%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(G%5Bu%5D%5Bv%5D%3D%3D1%20%26%26%20colorArr%5Bv%5D%3D%3DcolorArr%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20we%20reach%20here%2C%20then%20all%20adjacent%20vertices%20can%0A%20%20%20%20%20%20%20%20%2F%2F%20%20be%20colored%20with%20alternate%20color%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20program%20to%20test%20above%20function%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20G%5B%5D%5B%5D%20%3D%20%7B%7B0%2C%201%2C%200%2C%201%7D%2C%0A%20%20%20%20%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%20%20%20%20%7B0%2C%201%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%200%2C%201%2C%200%7D%0A%20%20%20%20%20%20%20%20%7D%3B%0A%20%20%20%20%20%20%20%20Bipartite%20b%20%3D%20new%20Bipartite()%3B%0A%20%20%20%20%20%20%20%20if%20(b.isBipartite(G%2C%200))%0A%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%22)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Contributed%20by%20Aakash%20Hasija\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Yes<\/pre>\n<p>The above algorithm works only if the graph is strongly connected. In above code, we always start with source 0 and assume that vertices are visited from it. One important observation is a graph with no edges is also Bipiartite. Note that the Bipartite condition says all edges should be from one set to another.<\/p>\n<p>We can extend the above code to handle cases when a graph is not connected. The idea is repeatedly call above method for all not yet visited vertices.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20out%20whether%20a%20given%20graph%20is%20Bipartite%20or%20not.%0A%2F%2F%20It%20works%20for%20disconnected%20graph%20also.%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Aconst%20int%20V%20%3D%204%3B%0A%20%0A%2F%2F%20This%20function%20returns%20true%20if%20graph%20G%5BV%5D%5BV%5D%20is%20Bipartite%2C%0A%2F%2F%20else%20false%0Abool%20isBipartiteUtil(int%20G%5B%5D%5BV%5D%2C%20int%20src%2C%20int%20colorArr%5B%5D)%0A%7B%0A%20%20%20%20colorArr%5Bsrc%5D%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20queue%20(FIFO)%20of%20vertex%20numbers%20and%20enqueue%0A%20%20%20%20%2F%2F%20source%20vertex%20for%20BFS%20traversal%0A%20%20%20%20queue%20%3Cint%3E%20q%3B%0A%20%20%20%20q.push(src)%3B%0A%20%0A%20%20%20%20%2F%2F%20Run%20while%20there%20are%20vertices%20in%20queue%20(Similar%20to%20BFS)%0A%20%20%20%20while%20(!q.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Dequeue%20a%20vertex%20from%20queue%20(%20Refer%20http%3A%2F%2Fgoo.gl%2F35oz8%20)%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20q.front()%3B%0A%20%20%20%20%20%20%20%20q.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20all%20non-colored%20adjacent%20vertices%0A%20%20%20%20%20%20%20%20for%20(int%20v%20%3D%200%3B%20v%20%3C%20V%3B%20%2B%2Bv)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20An%20edge%20from%20u%20to%20v%20exists%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20destination%20v%20is%20not%20colored%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(G%5Bu%5D%5Bv%5D%20%26%26%20colorArr%5Bv%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Assign%20alternate%20color%20to%20this%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20adjacent%20v%20of%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20colorArr%5Bv%5D%20%3D%201%20-%20colorArr%5Bu%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q.push(v)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20An%20edge%20from%20u%20to%20v%20exists%20and%20destination%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20v%20is%20colored%20with%20same%20color%20as%20u%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(G%5Bu%5D%5Bv%5D%20%26%26%20colorArr%5Bv%5D%20%3D%3D%20colorArr%5Bu%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%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%2F%20If%20we%20reach%20here%2C%20then%20all%20adjacent%20vertices%20can%0A%20%20%20%20%2F%2F%20be%20colored%20with%20alternate%20color%0A%20%20%20%20return%20true%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20true%20if%20G%5B%5D%5B%5D%20is%20Bipartite%2C%20else%20false%0Abool%20isBipartite(int%20G%5B%5D%5BV%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20color%20array%20to%20store%20colors%20assigned%20to%20all%0A%20%20%20%20%2F%2F%20veritces.%20Vertex%2F%20number%20is%20used%20as%20index%20in%20this%0A%20%20%20%20%2F%2F%20array.%20The%20value%20\u2032-1\u2019%20of%20%20colorArr%5Bi%5D%20is%20used%20to%0A%20%20%20%20%2F%2F%20ndicate%20that%20no%20color%20is%20assigned%20to%20vertex%20\u2019i\u2019.%0A%20%20%20%20%2F%2F%20The%20value%201%20is%20used%20to%20indicate%20first%20color%20is%0A%20%20%20%20%2F%2F%20assigned%20and%20value%200%20indicates%20second%20color%20is%0A%20%20%20%20%2F%2F%20assigned.%0A%20%20%20%20int%20colorArr%5BV%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20colorArr%5Bi%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20This%20code%20is%20to%20handle%20disconnected%20graoh%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%20if%20(colorArr%5Bi%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20if%20(isBipartiteUtil(G%2C%20i%2C%20colorArr)%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20return%20true%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20G%5B%5D%5BV%5D%20%3D%20%7B%7B0%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%20%20%20%20%7B0%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%0A%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20isBipartite(G)%20%3F%20cout%20%3C%3C%20%22Yes%22%20%3A%20cout%20%3C%3C%20%22No%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Yes<\/pre>\n<p>Time Complexity of the above approach is same as that Breadth First Search. In above implementation is O(V^2) where V is number of vertices. If graph is represented using adjacency list, then the complexity becomes O(V+E).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Java Algorithm &#8211; Check whether a given graph is Bipartite or not &#8211; Graph Algorithm &#8211; A Bipartite Graph is a graph whose vertices can be divided<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,74168,73906,2139],"tags":[78028,78022,78026,78029,78023,78021,78030,78065,78024,78031,78025,78027,78032],"class_list":["post-26267","post","type-post","status-publish","format-standard","hentry","category-coding","category-dfs-and-bfs","category-graph-algorithms","category-java","tag-bipartite-graph-algorithm","tag-bipartite-graph-algorithm-using-dfs","tag-bipartite-graph-applications","tag-bipartite-graph-c","tag-bipartite-graph-code-in-c","tag-bipartite-graph-example","tag-bipartite-graph-example-ppt","tag-bipartite-graph-geeksforgeeks","tag-bipartite-graph-matching","tag-bipartite-graph-pdf","tag-check-if-a-graph-is-bipartite-using-bfs","tag-complete-bipartite-graph","tag-tripartite-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26267","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=26267"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26267\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}