Is Graph Bipartite?

To determine if a graph is bipartite, we can use graph coloring where we attempt to color the graph using two colors (e.g., 0 and 1). If we can successfully color the graph such that no two adjacent nodes have the same color, then the graph is bipartite.

Here’s how we can achieve this:

Initialize Colors: Create an array colors to keep track of the color of each node. Initially, all nodes are uncolored, which we can represent with -1.
DFS or BFS Traversal: For each uncolored node, we can start a Depth First Search (DFS) or Breadth First Search (BFS) to color the graph. If we find a conflict where two adjacent nodes have the same color, return False.
Return True: If we successfully color the entire graph without conflicts, return True.

Code using DFS:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        colors = [-1] * n  # -1 represents uncolored

        # DFS function to color the graph
        def dfs(node, color):
            # If the node is already colored, check for consistency
            if colors[node] != -1:
                return colors[node] == color

            # Color the current node
            colors[node] = color

            # Visit all neighbors and try to color them with the opposite color
            for neighbor in graph[node]:
                if not dfs(neighbor, 1 - color):
                    return False

            return True

        # Try to color each uncolored node
        for i in range(n):
            if colors[i] == -1 and not dfs(i, 0):
                return False

        return True

Example

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: Nodes {0, 2} can be colored with 0, and nodes {1, 3} can be colored with 1. All adjacent nodes have different colors.

Insights

Graph Traversal: Both DFS and BFS can be used to solve this problem. The choice depends on the specific needs and preferences.
Complexity: The time complexity is (O(n + e)), where (n) is the number of nodes, and (e) is the number of edges. This is because we visit each node and each edge once.
Use of Colors: The use of colors as a metaphor for partitioning the nodes into two sets helps to simplify the problem and make the code more intuitive.

Identifying Problem Isomorphism

“Is Graph Bipartite?” is about checking if a given graph is bipartite, that is, can be divided into two sets of vertices such that no vertex in a set is connected with any other vertex of the same set.

A simpler problem which shares this theme of categorizing or grouping elements is “Partition Labels”. Here, the task is to partition a string into as many parts as possible so that each letter appears in at most one part.

An approximate isomorphic problem is “Flower Planting With No Adjacent”. In this problem, you are asked to assign a flower type to each garden such that, for any two gardens connected by a path, they have different types of flowers.

A more complex problem is “Cut Off Trees for Golf Event”. This problem involves determining the minimum total distance needed to cut down all trees in a forest where each tree is represented as a cell in a 2D grid. The complexity comes from the constraints that you can only move up, down, left, and right and you cannot move through trees that are yet to be cut down.

So, from simplest to more complex:

“Partition Labels” - Partition a string into as many parts as possible so that each letter appears in at most one part.
“Is Graph Bipartite?” - Check if a given graph is bipartite.
“Flower Planting With No Adjacent” - Assign a flower type to each garden such that no two adjacent gardens have the same type of flower.
“Cut Off Trees for Golf Event” - Determine the minimum total distance needed to cut down all trees in a forest represented as a 2D grid.

Define the Terms

Graph Bipartite

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.

Define the Interface Input: adjacency list (array of arrays) Output: boolean

Analyze the Input and Output

Input: 0 1 2 3 [[1,2,3],[0,2],[0,1,3],[0,2]]

Why is it false for example 1? You cannot have common nodes for both sets.

Partition such that the constraints all of your neighbors are in the other set. There are direct connection to the neighbor in the same set.

Why is it true for example 2? Set A Set B 0 1 2 3

Example 2

Set A Set B 0 0 3 1 2 2

Identify the Invariants

Once you assign a vertext to a set, you cannot change it.

Identify the constraints

graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1 (vertices are between 0 and 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. (bidirectional)

Search the Problem Space

Classify the Problem Color Graph We only have two colors (R/B) Assignment Problem Constraint Satisfaction Problem

Analyze the Examples Neighbors of neigbors should not have the same color. Return false immediately.

Solve the Problem by Hand One node -> false Two nodes -> false

Handle disconnected components.

Describe the Pattern

Distill the Observations to Create Insights Graph is given. We don’t have to construct a graph from the edges. We can traverse. On the fly we can start coloring the graph.

Identify the states of the variables. The variables are the vertices. Domains of the variables: {A, B} No adjacent vertices can belong to the same set.

Initial state of nodes can be: - it is not colored - it is colored

Start from 0 O is colored A Neighbors of 0 is colored B (1, 3) 1 is already colored, do nothing Check the neighbors of 1, (2,0) Color 2 as A

Return true

Start from 0 O is colored A Neighbors of 0 is colored B (1,2,3) Visit 1 1 is already colored, do nothing Return false because 2 is a neighbor of 1 and is colored the same as 1, This violates the constraint.

Check the neighbors of 1, (2,0) Color 2 as A

Brute Force Approach

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

How do we traverse this graph? DFS State of the vertices
How are we going to detect the violation of constraint?

If the current node is the same color as its immediate neighbor, return false

Key Takeaways

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# @param {Integer[][]} graph
# @return {Boolean}
def is_bipartite(graph)
  n = graph.size
  color = [-1]*n
  # 0 - A, 1 - B 
  
  for start in (0...n)
     if color[start] == -1
         stack = []
         stack.push(start)
         color[start] = 0

         while !stack.empty?
            vertex = stack.pop

            graph[vertex].each do |neighbor|
               if color[neighbor] == -1
                  stack.push(neighbor)
                  color[neighbor] = color[vertex] ^ 1
               elsif color[neighbor] == color[vertex]
                   return false
               end
            end
         end
     end
  end

  return true
end

The graph is an adjacency list, the indices are the veritces the neighbors are the array at that index.

Example 1:

We can start traversing the graph from vertex 0.
Color vertex 0 as R
For all neighbors of 0, color it B

Traverse from 0 and color 0 and its neighbors

0 - R 1 - B 2 - B (2 cannot be colored R or B) Return false 3 - B

Example 2:

We can start traversing the graph from vertex 0.
Color vertex 0 as R
For all neighbors of 0, color it B

0 - R 1 - B 3 - B

Consider vertex 1: It is already colored. For all neighbors of 1, color it R 0 - R (already colored R - no conflict) 2 - R
Consider vertex 2 It is already colored. For all neighbors of 2, color it B 1 is already B (nothing to do) 3 is already B (nothing to do)
Consider the last vertex 3 It is B For all neighbors of 3, color must be R 0 is already R (nothing to do) 2 is already R (nothing to do)

We have traversed and colored all vertices without conflict. Return true.

What type of graph traversal ?

Not Provided in The Problem Statement

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# @param {Integer[][]} graph
# @return {Boolean}
def is_bipartite(graph)
  n = graph.size
  color = [-1] * n
  
  for start in (0...n)
    if color[start] == -1
      stack = []
      stack.push(start)
      color[start] = 0

      while !stack.empty?
        vertex = stack.pop
        graph[vertex].each do |neighbor|
          if color[neighbor] == -1
            stack.push(neighbor)
            color[neighbor] = color[vertex] ^ 1
          elsif color[neighbor] == color[vertex]
            return false
          end
        end

      end
    end
  end
  
  return true
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from typing import List
from collections import deque

class Solution:
    def isBipartite(self, gr: List[List[int]]) -> bool:
        n = len(gr)
        color = [0] * n

        for node in range(n):
            if color[node] != 0:
                continue

            q = deque()
            q.append(node)
            color[node] = 1

            while q:
                cur = q.popleft()

                for ne in gr[cur]:
                    if color[ne] == 0:
                        color[ne] = -color[cur]
                        q.append(ne)
                    elif color[ne] != -color[cur]:
                        return False

        return True

Identifying Problem Isomorphism

“Is Graph Bipartite?” deals with determining if a graph is bipartite, i.e., whether it can be divided into two disjoint sets such that every edge connects a vertex in one set with a vertex in the other set.

A closely related problem to this one is LeetCode problem “886. Possible Bipartition”. This problem also deals with partitioning a set of entities (in this case, people with certain dislikes) into two disjoint sets such that certain conditions (in this case, no pair of people who dislike each other are in the same group) are met.

In both problems, we are essentially applying the concept of bipartitioning in graph theory and checking whether such a partition is possible given certain conditions. Thus, while the context and specific conditions vary between the two problems, the underlying concept and problem-solving approach remain very similar. Hence, “886. Possible Bipartition” can be seen as an approximate isomorphic problem to “785. Is Graph Bipartite?”.

Problem Classification

Language Agnostic Coding Drills

Concept 1 - Variable and List Initialization: Understanding how to declare variables and initialize lists.

Concept 2 - for loop: Understanding how to use a for loop to iterate over a range or collection of items.

Concept 3 - if, else and continue statements: Understanding how to use if, else statements and continue keyword to control the flow of the code.

Concept 4 - Importing modules and using functions from them: Understanding how to import modules (collections in this case) and how to use functions or data structures (deque here) from them.

Concept 5 - Appending and removing elements from a data structure: Understanding how to append elements to a list and how to add and remove elements from a deque.

Concept 6 - Nested for loop: Understanding how to use nested for loops, where one loop is inside another.

Concept 7 - Using indices to access and manipulate elements in a list: Understanding how to access and manipulate elements in a list using their indices.

Concept 8 - Function or method declaration and usage: Understanding how to declare a function or method and how to call it.

Concept 9 - Algorithms and Graph Theory (Bipartite Check): Understanding the concept of a bipartite graph and the algorithm to check if a graph is bipartite or not.

The concepts should be arranged in the following order of increasing level of difficulty:

Variable and List Initialization
if, else and continue statements
for loop
Importing modules and using functions from them
Appending and removing elements from a data structure
Using indices to access and manipulate elements in a list
Nested for loop
Function or method declaration and usage
Algorithms and Graph Theory (Bipartite Check)

Targeted Drills in Python

Concept 1 - Variable and List Initialization:

1
2
3
4
# Drill: Initialize a list of size 10 with all elements as 0
list_size = 10
zero_list = [0] * list_size
print(zero_list)

Concept 2 - for loop:

1
2
3
# Drill: Iterate over a range of numbers from 1 to 10 and print each number
for i in range(1, 11):
    print(i)

Concept 3 - if, else and continue statements:

1
2
3
4
5
# Drill: Loop through numbers 1-10, print the number if it's odd, otherwise continue
for i in range(1, 11):
    if i % 2 == 0:
        continue
    print(i)

Concept 4 - Importing modules and using functions from them:

1
2
3
4
# Drill: Import the math module and print the square root of a number
import math
num = 9
print(math.sqrt(num))

Concept 5 - Appending and removing elements from a data structure:

1
2
3
4
5
6
7
8
# Drill: Create a deque, append elements and popleft
from collections import deque

d = deque()
d.append('Python')
d.append('Java')
print(d.popleft())
print(d)

Concept 6 - Nested for loop:

1
2
3
4
5
6
7
# Drill: Print a 2D matrix using nested for loop
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

for row in matrix:
    for element in row:
        print(element, end=" ")
    print()

Concept 7 - Using indices to access and manipulate elements in a list:

1
2
3
4
5
# Drill: Increment the first and last elements of a list by 1
my_list = [1, 2, 3, 4, 5]
my_list[0] += 1
my_list[-1] += 1
print(my_list)

Concept 8 - Function or method declaration and usage:

1
2
3
4
5
# Drill: Create a function that returns the sum of two numbers
def sum_two_numbers(a, b):
    return a + b

print(sum_two_numbers(3, 4))

Concept 9 - Algorithms and Graph Theory (Bipartite Check):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Drill: Given a graph represented as an adjacency matrix, check if it is bipartite
from collections import deque

def is_bipartite(graph):
    n = len(graph)
    color = [0] * n
    for node in range(n):
        if color[node] != 0:
            continue
        q = deque()
        q.append(node)
        color[node] = 1
        while q:
            cur = q.popleft()
            for neigh in range(n):
                if graph[cur][neigh] == 1:
                    if color[neigh] == 0:
                        color[neigh] = -color[cur]
                        q.append(neigh)
                    elif color[neigh] != -color[cur]:
                        return False
    return True

graph = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]
print(is_bipartite(graph))

title: Bipartite Graph excerpt: Check if a graph is 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. 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.

Thought Process

Define the Term. What is bipartite?

Graph Bipartite: 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.

Define the Interface

Input: adjacency list (array of arrays) Output: boolean

How do we know it is bipartite?
How to interpret the input?

Analyze the Input and Output

Input:
    0      1     2       3
[[1,2,3],[0,2],[0,1,3],[0,2]]

Why is it false for example 1? You cannot have common nodes for both sets. Partition such that the constraints of all of your neighbors are in the other set. There are direct connections to the neighbor in the same set.

Why is it true for example 2?

  Set A   Set B
  0        1
  2        3

Example 2

Set A   Set B
0        0
3        1
2        2

Neighbors of neighbors should not have the same color. Return false immediately.

Identify the constraints

graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1 (vertices are between 0 and 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. (bidirectional)

Identify the Invariants

Invariant: If you haven’t seen something and you encounter it during DFS, the vertex can be put into either A or B. Once you assign a vertex to a set, you cannot change it.

Subsets => Is this a clue that we can use Union Find?

Solve the Problem by Hand

One node -> false Two nodes -> false

Handle disconnected components.

Classify the Problem

Color Graph
We only have two colors (R/B)
Assignment Problem

Is there an alternative approach?

Brute Force Approach

There are two subsets (A, B)
Identify the set to which a vertex belongs to
Pick the first vertex and put them into one of the subsets (either A or B) (u)
Find the edge of first vertex, and put the vertex v into the other subset
Condition for checking if the graph is not bipartite:
- Start with 0, push into a Set A
- Put 0 into set A
- The connections of A must be in B. Put them in B.

Cases

Case 1

You have already placed the vertex in the set

Case 2

It is not already in the set

Take vertex 0, it is color A
Its neighbors color is B
If you start DFS from the node that is in a Set, if you have not seen it before you can put it in either A or B.

The graph is an adjacency list, the indices are the vertices the neighbors are the array at that index.

Example 1:

We can start traversing the graph from vertex 0.
Color vertex 0 as R
For all neighbors of 0, color it B

Traverse from 0 and color 0 and its neighbors

0 - R
1 - B
2 - B (2 cannot be colored R or B) Return false
3 - B

Example 2:

We can start traversing the graph from vertex 0.
Color vertex 0 as R
For all neighbors of 0, color it B

0 - R
1 - B
3 - B

Consider vertex 1: It is already colored. For all neighbors of 1, color it R 0 - R (already colored R - no conflict) 2 - R
Consider vertex 2 It is already colored. For all neighbors of 2, color it B 1 is already B (nothing to do) 3 is already B (nothing to do)
Consider the last vertex 3 It is B For all neighbors of 3, color must be R 0 is already R (nothing to do) 2 is already R (nothing to do)

We have traversed and colored all vertices without conflict. Return true.

What type of graph traversal? This is not provided in the problem statement.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# @param {Integer[][]} graph
# @return {Boolean}
def is_bipartite(graph)
  n = graph.size
  color = [-1] * n
  
  for start in (0...n)
    if color[start] == -1
      stack = []
      stack.push(start)
      color[start] = 0
      
      while !stack.empty?
        vertex = stack.pop
        graph[vertex].each do |neighbor|
          if color[neighbor] == -1
            stack.push(neighbor)
            color[neighbor] = color[vertex] ^ 1
          elsif color[neighbor] == color[vertex]
            return false
          end
        end
        
      end
    end
  end
  
  return true
end

Distill the Observations to Create Insights

Graph is given. We don’t have to construct a graph from the edges. We can traverse. On the fly we can start coloring the graph.

Identify the states of the variables.

The variables are the vertices.
Domains of the variables: {A, B}
No adjacent vertices can belong to the same set.

Initial state of nodes can be:

It is not colored
It is colored

Start from 0
O is colored A
Neighbors of 0 is colored B (1, 3)
1 is already colored, do nothing
Check the neighbors of 1, (2,0)
Color 2 as A
  
Return true

Start from 0
O is colored A
Neighbors of 0 is colored B (1,2,3)
Visit 1
1 is already colored, do nothing
Return false because 2 is a neighbor of 1 and is
colored the same as 1, This violates the constraint.

Check the neighbors of 1, (2,0)
Color 2 as A

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Solution Outline

How do we traverse this graph? DFS State of the vertices
How are we going to detect the violation of constraint?

If the current node is the same color as its immediate neighbor, return false.

Key Takeaways

A vertex in set A indirectly connects a vertex in its own set via Set B
Using the stack for the iterative way to implement the DFS
If you don’t use an inner while with stack, you will fail to identify the constraint violation

DFS using Recursion

Every time we call the recursive function, pass in the next color. Color should be a global variable. This code passes only example 2:

1
2
3
4
5
6
7
graph[start].each do |neighbor|
  if color[neighbor] == -1
    color[neighbor] = color[start] ^ 1 
  elsif color[neighbor] == color[start]
    return false
  end
end

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# @param {Integer[][]} graph
# @return {Boolean}
def is_bipartite(graph)
  n = graph.size
  color = [-1]*n
  # 0 - A, 1 - B 
  
  for start in (0...n)
    if color[start] == -1
      stack = []
      stack.push(start)
      color[start] = 0
         
      while !stack.empty?
        vertex = stack.pop
             
        graph[vertex].each do |neighbor|
          if color[neighbor] == -1
            stack.push(neighbor)
            color[neighbor] = color[vertex] ^ 1
          elsif color[neighbor] == color[vertex]
            return false
          end
        end
      end
    end
  end
    
  return true
end