This is our solution and implementation to problem #785: Is Graph Bipartite? on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Is Graph Bipartite? on LeetCode.
Problem Analysis
The problem gives us a 2D array as input, where each row represents a vertex and each cell in that row indicates a vertex which it connects to. This is similar to an adjacency matrix in concept, but it does not include entries for vertex which each vertex does not connect to. The problem gives a definition of a bipartite graph as a graph where there are exactly 2 sets of vertices and a set of edges where every edge connects a vertex from the first set with one from the second set. Based on this definition, we can infer some additional properties of such as graph:
- The two sets to not need to be the same size. For example, a bipartite graph can have one center vertex where every other vertex connects to it and only it.
- Since every edge must connect a vertex from each set, we cannot have any edges which connect a node to another node in its own set.
- As a consequence, every vertex u which is connected to a vertex v must belong in the other set.
Based on these observations, particularly the second point, we can determine whether a graph is bipartite or not based on whether or not it violates those conditions. When creating the implementation, we must account for a few edge cases:
- A graph with no nodes.
- A graph with only two nodes.
- A graph which is not connected.
Implementation Strategy
We can use a breadth-first search algorithm to iterate over the nodes and add each node to its corresponding set. The entry node can be assigned to set A, then its connected nodes to B, their connected nodes to A, etc. In the case of disconnected graphs, we can take this action for each connected subgraph. If, during the traversal, we encounter a node which has already been visited, we can ensure the visited node is in the opposite set of the current node. If it is not, we can return false immediately. If this never happens, we can return true. We will implement this algorithm using a HashMap to record which set each vertex belongs to.
Space and Time Complexity
We will define the space and time complexity in terms of the number of vertices v and the number of edges e. The space complexity is O(v), as we are using a HashMap to map each vertex with a boolean indicating if it is a member of set A or set B. We will also be using an additional HashSet and Queue for the graph traversal, both of which are related to the number of vertices. The time complexity is O(v+e), which is the same as the time complexity for a breadth-first search.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.