{x}
blog image

Is Graph Bipartite?

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 contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such 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 == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] does not contain u.
  • All the values of graph[u] are unique.
  • If graph[u] contains v, then graph[v] contains u.

Solution Explanation:

This problem asks whether a given graph is bipartite. A bipartite graph is one whose nodes can be divided into two disjoint sets, say A and B, such that every edge connects a node in A to a node in B (no edges connect nodes within the same set).

Two main approaches are commonly used to solve this problem: Depth-First Search (DFS) and Union-Find. Both approaches are explained below.

Approach 1: Depth-First Search (DFS)

This approach uses a coloring technique. We assign colors (e.g., 1 and 2) to nodes during DFS traversal. If we encounter a conflict (adjacent nodes having the same color), the graph is not bipartite.

Algorithm:

  1. Initialization: Create a color array to store the color of each node. Initialize all nodes to 0 (uncolored).
  2. Iteration: Iterate through each node in the graph. If a node is uncolored, start a DFS traversal from that node.
  3. DFS Traversal:
    • Assign a color (e.g., 1) to the current node.
    • For each neighbor of the current node:
      • If the neighbor is uncolored, recursively call DFS on the neighbor with the opposite color (3 - current color). If the recursive call returns false, the graph is not bipartite, so return false.
      • If the neighbor has the same color as the current node, the graph is not bipartite, so return false.
  4. Result: If the DFS completes without finding any conflicts, the graph is bipartite; return true.

Time Complexity Analysis:

The DFS algorithm visits each node and edge at most once. Therefore, the time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.

Space Complexity Analysis:

The space complexity is O(V) due to the color array used to store the colors of nodes. The recursive call stack during DFS can also contribute to space complexity, which is at most O(V) in the worst-case (a very deep graph).

Approach 2: Union-Find (Disjoint Set)

This approach leverages the Union-Find data structure to determine if a graph is bipartite. The idea is that if two connected nodes end up in the same set, the graph can't be bipartite.

Algorithm:

  1. Initialization: Create a parent array for the Union-Find data structure. Initialize each node's parent to itself.
  2. Iteration: Iterate through each node u in the graph. For each neighbor v of u:
    • Find the root parent of u and v using the find function of the Union-Find structure.
    • If the roots are the same, it means u and v belong to the same set, so the graph is not bipartite; return false.
    • Otherwise, union the sets containing u and v using the union function.
  3. Result: If the loop completes without finding any conflicts, the graph is bipartite; return true.

Time Complexity Analysis:

Using path compression and union by rank optimizations in Union-Find, the amortized time complexity is nearly O(α(V)), where α is the inverse Ackermann function, which grows extremely slowly and can be considered effectively constant for all practical purposes. The overall complexity is dominated by iterating through the edges, leading to a time complexity of O(E).

Space Complexity Analysis:

The space complexity is O(V) for the parent array in the Union-Find structure.

Code Examples (Multiple Languages)

The code examples for both approaches (DFS and Union-Find) are provided in the original response. Remember to adapt the code to your specific environment and coding standards. The provided codes illustrate efficient implementations of both approaches in various languages. Note that the Union-Find approach, while theoretically having potentially better complexity in some cases, may not always be faster in practice than a well-optimized DFS for smaller graphs due to the overhead of Union-Find operations. DFS is often simpler to implement and understand.