Is Graph Bipartite?
Problem Description
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:
- There are no self-edges (
graph[u]does not containu). - There are no parallel edges (
graph[u]does not contain duplicate values). - If
vis ingraph[u], thenuis ingraph[v](the graph is undirected). - The graph may not be connected, meaning there may be two nodes
uandvsuch that there is no path between them.
A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
Return true if and only if it is bipartite.
Example 1:
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.
Example 2:
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.
Constraints:
graph.length == n1 <= n <= 1000 <= graph[u].length < n0 <= graph[u][i] <= n - 1graph[u]does not containu.- All the values of
graph[u]are unique. - If
graph[u]containsv, thengraph[v]containsu.
Solve it on LeetCode
Approaches
1. Depth First Search (DFS) with Two Colors
Intuition:
A graph is bipartite if its nodes can be divided into two independent sets such that no two graph nodes within the same set are adjacent. We can utilize a two-color technique, where we attempt to color the graph using two colors and verify that no two adjacent nodes have the same color. This can be efficiently done using Depth First Search (DFS).
Steps:
- Initialize a color array to keep track of the color assigned to each node (e.g., use -1, 0, and 1, where -1 indicates uncolored).
- Traverse each node in the graph. If a node is uncolored, apply DFS to color it and its connected components.
- During DFS, ensure no two adjacent nodes have the same color. If two adjacent nodes share a color, the graph is not bipartite.
- If all nodes can be properly colored, then the graph is bipartite.
Code:
- Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
- Space Complexity: O(V) for storing the color of each node.
2. Breadth First Search (BFS) with Two Colors
Intuition:
Another way to solve the problem using two-coloring is to utilize Breadth First Search (BFS). This approach uses a queue to explore each level of the graph and ensures that adjacent nodes are assigned different colors.
Steps:
- Create a color array similar to the DFS approach.
- Use a queue to perform BFS on each uncolored component of the graph.
- Attempt to color each node and its neighbors with alternating colors.
- If any adjacent nodes have the same color during BFS traversal, the graph is not bipartite.
Code:
- Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges (same as DFS).
- Space Complexity: O(V) for storing the color of each node and the queue.