Given a graph, check if given graph is bipartite graph or not. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
Below graph is a Bipartite Graph as we can divide it into two sets U and V with every edge having one end point in set U and the other in set V
It is possible to test whether a graph is bipartite or not using breadth-first search algorithm. There are two ways to check for Bipartite graphs –
1. A graph is bipartite graph if and only if it is 2-colorable.
While doing BFS traversal, each node in the BFS tree is given the opposite color to its parent. If there exists an edge connecting current vertex to a previously-colored vertex with the same color, then we can safely conclude that the graph is not bipartite.
2. A graph is bipartite graph if and only if it does not contain an odd cycle.
If a graph contains an odd cycle, we cannot divide the graph such that every adjacent vertex has different color. To check if a given graph is contains odd-cycle or not, we do a breadth-first search starting from an arbitrary vertex v. If in the BFS, we find an edge, both of whose end-points are in the same level, then the graph is not Bipartite and odd-cycle is found. Here, level of a vertex is its minimum distance from the starting vertex v. So, odd-level vertices will form one set and even-level vertices will form another.
Please note that if the graph has many connected components and each component bipartite, them the graph is bipartite graph. Below code assume that given graph is connected and checks if the graph contains an odd cycle or not.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <vector> #include <queue> using namespace std; // data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // construct a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int N) { // resize the vector to N elements of type vector<int> adjList.resize(N); // add edges to the undirected graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; // Perform BFS on graph starting from vertex v bool BFS(Graph const &graph, int v, int N) { // stores vertex is discovered or not vector<bool> discovered(N); // stores level of each vertex in BFS vector<int> level(N); // mark source vertex as discovered and // set its level to 0 discovered[v] = true, level[v] = 0; // create a queue to do BFS and enqueue // source vertex in it queue<int> q; q.push(v); // run till queue is not empty while (!q.empty()) { // pop front node from the queue v = q.front(); q.pop(); // do for every edge (v -> u) for (int u : graph.adjList[v]) { // if vertex u is explored for first time if (!discovered[u]) { // mark it discovered discovered[u] = true; // set level as level of parent node + 1 level[u] = level[v] + 1; // push the vertex into the queue q.push(u); } // if the vertex is already been discovered and // level of vertex u and v are same, then the // graph contains an odd-cycle & is not biparte else if (level[v] == level[u]) return false; } } return true; } // Determine if a given graph is Bipartite Graph or not int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {1, 2}, {2, 3}, {2, 8}, {3, 4}, {4, 6}, {5, 7}, {5, 9}, {8, 9} // if we add 2->4 edge, graph is becomes non-Bipartite }; // Number of nodes in the graph int N = 10; // create a graph from edges Graph graph(edges, N); // Do BFS traversal starting from vertex 1 if (BFS(graph, 1, N)) cout << "Bipartite Graph"; else cout << "Not a Bipartite Graph"; return 0; } |
Output:
Bipartite Graph
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
import java.util.*; // Data structure to store graph edges class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } }; // Class to represent a graph object class Graph { // An array of Lists to represent adjacency list List<List<Integer>> adjList = null; // Constructor Graph(List<Edge> edges, int N) { adjList = new ArrayList<>(N); for (int i = 0; i < N; i++) { adjList.add(i, new ArrayList<>()); } // add edges to the undirected graph for (int i = 0; i < edges.size(); i++) { int src = edges.get(i).source; int dest = edges.get(i).dest; // add an edge from source to destination adjList.get(src).add(dest); // add an edge from destination to source adjList.get(dest).add(src); } } } class BipartiteGraph { // Perform BFS on graph starting from vertex v public static boolean BFS(Graph graph, int v, int N) { // stores vertex is discovered or not boolean[] discovered = new boolean[N]; // stores level of each vertex in BFS int[] level = new int[N]; // mark source vertex as discovered and // set its level to 0 discovered[v] = true; level[v] = 0; // create a queue to do BFS and enqueue // source vertex in it Queue<Integer> q = new ArrayDeque<>(); q.add(v); // run till queue is not empty while (!q.isEmpty()) { // pop front node from queue and print it v = q.poll(); // do for every edge (v -> u) for (int u : graph.adjList.get(v)) { // if vertex u is explored for first time if (!discovered[u]) { // mark it discovered discovered[u] = true; // set level as level of parent node + 1 level[u] = level[v] + 1; // push the vertex into the queue q.add(u); } // if the vertex is already been discovered and // level of vertex u and v are same, then the // graph contains an odd-cycle & is not biparte else if (level[v] == level[u]) return false; } } return true; } public static void main(String[] args) { // vector of graph edges as per above diagram List<Edge> edges = Arrays.asList( new Edge(1, 2), new Edge(2, 3), new Edge(2, 8), new Edge(3, 4), new Edge(4, 6), new Edge(5, 7), new Edge(5, 9), new Edge(8, 9) // if we add 2->4 edge, graph is becomes non-Bipartite ); // Set number of vertices in the graph final int N = 10; // create a graph from edges Graph graph = new Graph(edges, N); // Do BFS traversal starting from vertex 1 if (BFS(graph, 1, N)) System.out.println("Bipartite Graph"); else System.out.println("Not a Bipartite Graph"); } } |
Output:
Bipartite Graph
The time complexity of above solution is O(n + m) where n is number of vertices and m is number of edges in the graph. Please note that O(m) may vary between O(1) and O(n2), depending on how dense the graph is.
References: https://en.wikipedia.org/wiki/Bipartite_graph
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
What’s point of getting bipartite graph ? What kind of problem I can solve by knowing this property?
Imagine a set of men and a set of women. Each man likes zero or more women and vice versa. The problem is to form couples in the way that maximizes matches. Or you need to keep busy a set of workers each of which is qualified to do some particular tasks. And so on.
Will it work for directed graph, that is not strongly connected but connected?
Line no. 22 throws a compilation error !
There should be
==instead of=in line 78Thanks Abhishek for bring this to our notice. We have corrected the typo. Happy coding 🙂
is more optimization possible?