algoadvance

You are given an n x n graph represented by an adjacency matrix, where graph[u] is a list of nodes v such that there is an edge between node u and node v. Return true if the graph is bipartite. A graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every edge in the graph connects a node in set A and a node in set B.

Clarifying Questions

  1. Is the graph connected?: No, the graph can be disconnected.
  2. Can the input size be very large?: Yes, the input size can be large, but it will typically fit within the constraints of LeetCode problems.
  3. Can the graph have self-loops or multiple edges between the same nodes?: No, the graph is an undirected simple graph.

Strategy

To determine if a graph is bipartite, we can use a two-coloring technique. We will try to color the graph using two colors such that no two adjacent nodes share the same color. This can be done using either Depth-First Search (DFS) or Breadth-First Search (BFS).

  1. Initialization:
    • Create a color array to keep track of the coloring of each node. Initialize all values to -1 indicating that no node is colored initially.
  2. BFS or DFS Traversal:
    • For each node, if it hasn’t been colored yet, color it with one color (say 0) and use BFS or DFS to attempt to color all its neighbors with the opposite color (say 1).
    • If we find a neighboring node that has already been colored with the same color, then the graph is not bipartite.
  3. Handle Unconnected Nodes:
    • The graph might be disconnected, so we must ensure we check all components of the graph.

Code

Here’s the implementation using BFS:

from collections import deque

def isBipartite(graph):
    n = len(graph)
    color = [-1] * n  # Color array to store colors of nodes, -1 means uncolored

    for start in range(n):
        if color[start] == -1:  # Uncolored node, start a BFS/DFS from here
            queue = deque([start])
            color[start] = 0  # Start coloring with 0
            
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        # Color with the opposite color
                        color[neighbor] = 1 - color[node]
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        # If neighbor has the same color, graph is not bipartite
                        return False
                        
    return True

Time Complexity

This ensures we handle both connected and disconnected components by initiating a BFS search from every uncolored node.

Try our interview co-pilot at AlgoAdvance.com