Is Graph Bipartite - Leetcode Solution

Problem: Given an undirected graph, return true if and only if it 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 has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example: Input: graph = [[1,3],[0,2],[1,3],[0,2]] Output: true Explanation: We can divide the vertices into two groups: {0, 2} and {1, 3}.

Solution: The idea is to use BFS traversal to color each node with either red or blue color, such that no two adjacent nodes have the same color. For this, we can start by picking a node from the graph and color it with red color. Then, we will add all its adjacent nodes to the queue and color them with blue color. We will continue this process until all the nodes in the graph are colored or we find a pair of adjacent nodes with the same color.

Algorithm:

1. Create an empty queue and a color array for all nodes initialized to -1.
2. Pick a node and color it with red (0).
3. Add the node to the queue.
4. While the queue is not empty, do the following: a. Dequeue the front node from the queue. b. Traverse all its adjacent nodes: i. If the adjacent node is not colored, assign it a color different from the current node and enqueue it. ii. If the adjacent node is already colored and the color is the same as the current node, return false.
5. If all nodes are colored such that no two adjacent nodes have the same color, return true.

Below is the Python code implementation for the same:

def isBipartite(self, graph: List[List[int]]) -> bool: n = len(graph) colors = [-1] * n # Colors for all nodes initialized to -1 (unassigned) for i in range(n): # Traverse all nodes in case of disconnected graph if colors[i] == -1: # If node is not colored yet, color it with red and add it to queue queue = [i] colors[i] = 0 while queue: u = queue.pop(0) # Dequeue the front node for v in graph[u]: # Traverse all adjacent nodes if colors[v] == -1: # If the node is not colored, color it with a different color and add it to queue colors[v] = 1 - colors[u] # Assign a different color (0 - red, 1 - blue) queue.append(v) elif colors[v] == colors[u]: # If the adjacent node is already colored and has the same color as the current node, return false return False return True # If all nodes are colored such that no two adjacent nodes have the same color, return true.

Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges in the graph. Space Complexity: O(V), where V is the number of vertices in the graph for the colors array.

1