We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Is Graph Bipartite?

Number: 801

Difficulty: Medium

Paid? No

Companies: Google, Samsung, Amazon, Uber, Microsoft, TikTok, Meta, Pinterest

Problem Description

Determine if a given undirected graph is bipartite, meaning its nodes can be partitioned into two disjoint sets such that every edge connects a node from one set to a node from the other. The graph is represented as an adjacency list and may be disconnected.

Key Insights

  • A graph is bipartite if you can assign two colors to each node such that no two adjacent nodes share the same color.
  • The challenge may require exploring disconnected components.
  • BFS or DFS can be used to attempt the two-coloring, and a conflict during coloring indicates the graph is not bipartite.
  • Union Find is an alternative approach, but BFS/DFS is more intuitive for graph coloring problems.

Space and Time Complexity

Time Complexity: O(V + E) where V is the number of nodes and E is the number of edges, since every node and edge is traversed at most once. Space Complexity: O(V), for the color array and the queue (or recursion stack) used in BFS (or DFS).

Solution

We use a BFS/DFS approach to assign colors (0 and 1) to nodes. A color array, initially set to -1 for all nodes, is maintained. For each unvisited node (color -1), we start a BFS (or DFS) and assign it an initial color (e.g., 0). For every visited neighbor, if it has not been colored, assign it the opposite color; if it is already colored with the same color as the current node, a conflict has occurred, and the graph is not bipartite. This method gracefully handles disconnected components by iterating over all nodes.

Code Solutions

# Using Breadth-First Search (BFS)
from collections import deque

def isBipartite(graph):
    n = len(graph)
    # color array: -1 means uncolored, 0 and 1 are the two colors.
    colors = [-1] * n
    
    # Iterate through each node to handle disconnected components
    for i in range(n):
        if colors[i] == -1:
            # Start BFS from node i with color 0
            queue = deque([i])
            colors[i] = 0
            while queue:
                node = queue.popleft()
                # Check each neighbor of the current node
                for neighbor in graph[node]:
                    if colors[neighbor] == -1:
                        # Assign the opposite color to the neighbor
                        colors[neighbor] = 1 - colors[node]
                        queue.append(neighbor)
                    elif colors[neighbor] == colors[node]:
                        # Found a neighbor with the same color: not bipartite
                        return False
    return True

# Example usage:
if __name__ == '__main__':
    graph_example = [[1,3],[0,2],[1,3],[0,2]]
    print(isBipartite(graph_example))  # Expected output: True
← Back to All Questions