Check whether a given graph is Bipartite or not
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.
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.
Solution :
- It can be easily solve by vertex color algorithm where color is 2
- We alternatively color a vertex, it means
-
- If vertex color is red, its neighbours color would be yellow and neighbours’s neighbour color would be red again.
- During painting if we found that color of two adjacent vertices is same the graph is not Bipartite.
Note:
- It is possible to color a cycle graph with even cycle using two colors.
- It is not possible to color a cycle graph with odd cycle using two colors.
Latest Source Code:
Github: BipartiteGraphChecker.java
Output:
0 -> [1, 3] 1 -> [0, 2] 2 -> [1, 3] 3 -> [0, 2] Is Graph Bipartite: true