onenoughtone

Bipartite Graph Pattern

What is a Bipartite Graph?

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in the first set to a vertex in the second set.

In other words, a graph is bipartite if its vertices can be colored using two colors such that no adjacent vertices have the same color.

Problem Statement

Given an undirected graph, determine if it is bipartite.

Example 1:

Graph: 0 -- 1 -- 2 -- 3 -- 0

Is bipartite: true
(Color 0 and 2 with one color, 1 and 3 with another color)

Example 2:

Graph: 0 -- 1 -- 2 -- 0

Is bipartite: false
(Cannot color the vertices with two colors)

BFS Approach

Initialize a colors array with all vertices uncolored (-1)
For each uncolored vertex in the graph:
- Start BFS from this vertex and color it with color 0
- For each neighbor, color it with the opposite color of its parent
- If a neighbor is already colored with the same color as its parent, the graph is not bipartite
If all vertices can be colored properly, the graph is bipartite

Implementation

Here's an implementation of the bipartite graph checking algorithm using BFS:

Time and Space Complexity

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.

Related Problem: Possible Bipartition

A related problem is the Possible Bipartition problem, where we need to determine if we can divide a group of people into two groups such that no two people who dislike each other are in the same group.

Previous Next

Pattern 4: Bipartite Graph

Learn how to use BFS to check if a graph is bipartite by coloring its vertices with two colors.

What is a Bipartite Graph?

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in the first set to a vertex in the second set.

In other words, a graph is bipartite if its vertices can be colored using two colors such that no adjacent vertices have the same color.

Examples:

Bipartite Graph:
0 -- 1 -- 2 -- 3 -- 0

Coloring: Color 0 and 2 with one color, 1 and 3 with another color.

Explanation: We can divide the vertices into two sets {0, 2} and {1, 3} such that all edges connect vertices from different sets.

Non-Bipartite Graph:
0 -- 1 -- 2 -- 0

Not Bipartite: Cannot color the vertices with two colors.

Explanation: This is a cycle of length 3, which cannot be colored with two colors because if we color 0 and 2 with one color, then 1 must be colored with the other color, but then 0 and 2 are adjacent and have the same color.

Properties and Applications

Key Properties

A graph is bipartite if and only if it does not contain an odd-length cycle
All trees are bipartite
A complete bipartite graph is a bipartite graph where every vertex in the first set is connected to every vertex in the second set

Real-world Applications

Matching problems (e.g., job assignments, student-teacher pairings)
Network flow problems
Scheduling problems (e.g., assigning tasks to processors)
Social network analysis (e.g., dividing people into two groups with no conflicts)

The BFS Approach for Checking Bipartiteness

1Initialize

Initialize a colors array with all vertices uncolored (-1). We'll use two colors (0 and 1) to color the vertices.

2Start BFS

For each uncolored vertex, start BFS from it and color it with color 0. This handles disconnected graphs.

3Color Neighbors

For each neighbor of the current vertex, color it with the opposite color (1 - current color). If it's already colored, check for conflicts.

4Check Conflicts

If a neighbor is already colored with the same color as the current vertex, the graph is not bipartite. Otherwise, continue BFS.

Implementation

Here's an implementation of the bipartite graph checking algorithm using BFS:

isBipartite.js

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function isBipartite(graph) {
  const n = graph.length;
 
  // Initialize colors array with -1 (uncolored)
  const colors = Array(n).fill(-1);
 
  // Try to color the graph starting from each uncolored vertex
  for (let i = 0; i < n; i++) {
    // If this vertex is uncolored and we can't color it properly
    if (colors[i] === -1 && !bfsColorGraph(graph, i, colors)) {
      return false;
    }
  }
 
  // If we can color all vertices properly, the graph is bipartite
  return true;
}
 
function bfsColorGraph(graph, start, colors) {
  // Queue for BFS
  const queue = [start];
 
  // Color the start vertex with color 0
  colors[start] = 0;
 
  // While there are vertices in the queue
  while (queue.length > 0) {
    // Dequeue a vertex from the queue
    const current = queue.shift();
 
    // Get all adjacent vertices of the dequeued vertex
    for (const neighbor of graph[current]) {
      // If this adjacent vertex is uncolored
      if (colors[neighbor] === -1) {
        // Color it with the opposite color of the current vertex
        colors[neighbor] = 1 - colors[current];
        queue.push(neighbor);
      }
      // If this adjacent vertex is already colored with the same color as the current vertex
      else if (colors[neighbor] === colors[current]) {
        // The graph is not bipartite
        return false;
      }
    }
  }
 
  // If we can color all vertices properly, this component is bipartite
  return true;
}
 
// Example usage:
const graph1 = [
  [1, 3],  // Vertex 0 is connected to vertices 1 and 3
  [0, 2],  // Vertex 1 is connected to vertices 0 and 2
  [1, 3],  // Vertex 2 is connected to vertices 1 and 3
  [0, 2]   // Vertex 3 is connected to vertices 0 and 2
];
 
const graph2 = [
  [1, 2, 3],  // Vertex 0 is connected to vertices 1, 2, and 3
  [0, 2],     // Vertex 1 is connected to vertices 0 and 2
  [0, 1, 3],  // Vertex 2 is connected to vertices 0, 1, and 3
  [0, 2]      // Vertex 3 is connected to vertices 0 and 2
];
 
console.log(isBipartite(graph1)); // Output: true
console.log(isBipartite(graph2)); // Output: false

Key Insight: We use BFS to color the graph with two colors (0 and 1). For each vertex, we color all its neighbors with the opposite color. If we encounter a neighbor that is already colored with the same color as the current vertex, the graph is not bipartite.

Time and Space Complexity

Time Complexity

O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Explanation: We visit each vertex once (O(V)) and explore each edge once (O(E)). Even though we run BFS multiple times, each vertex and edge is processed exactly once across all BFS calls.

Space Complexity

O(V), where V is the number of vertices in the graph.

Explanation: We need to store the colors array (O(V)) and the queue for BFS (O(V) in the worst case). Overall, the space complexity is O(V).

Common Pitfalls and Edge Cases

Disconnected Graphs

Make sure to check all components of the graph by running BFS from each uncolored vertex. A graph is bipartite only if all its components are bipartite.

Self-loops

A graph with self-loops (edges from a vertex to itself) cannot be bipartite because a vertex cannot be colored with two different colors.

Empty Graphs

An empty graph (no vertices) or a graph with no edges is trivially bipartite because there are no constraints on the coloring.

Related Problem: Possible Bipartition

possibleBipartition.js

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
function possibleBipartition(n, dislikes) {
  // Build the graph
  const graph = Array(n + 1).fill().map(() => []);
 
  for (const [a, b] of dislikes) {
    graph[a].push(b);
    graph[b].push(a);
  }
 
  // Initialize colors array with -1 (uncolored)
  const colors = Array(n + 1).fill(-1);
 
  // Try to color the graph starting from each uncolored vertex
  for (let i = 1; i <= n; i++) {
    // If this vertex is uncolored and we can't color it properly
    if (colors[i] === -1 && !bfsColorGraph(graph, i, colors)) {
      return false;
    }
  }
 
  // If we can color all vertices properly, the graph is bipartite
  return true;
}
 
function bfsColorGraph(graph, start, colors) {
  // Queue for BFS
  const queue = [start];
 
  // Color the start vertex with color 0
  colors[start] = 0;
 
  // While there are vertices in the queue
  while (queue.length > 0) {
    // Dequeue a vertex from the queue
    const current = queue.shift();
 
    // Get all adjacent vertices of the dequeued vertex
    for (const neighbor of graph[current]) {
      // If this adjacent vertex is uncolored
      if (colors[neighbor] === -1) {
        // Color it with the opposite color of the current vertex
        colors[neighbor] = 1 - colors[current];
        queue.push(neighbor);
      }
      // If this adjacent vertex is already colored with the same color as the current vertex
      else if (colors[neighbor] === colors[current]) {
        // The graph is not bipartite
        return false;
      }
    }
  }
 
  // If we can color all vertices properly, this component is bipartite
  return true;
}
 
// Example usage:
const n = 4;
const dislikes = [[1, 2], [1, 3], [2, 4], [3, 4]];
 
console.log(possibleBipartition(n, dislikes)); // Output: true

How it works: We model the problem as a graph where each person is a vertex, and there is an edge between two people if they dislike each other. We then check if this graph is bipartite. If it is, we can divide the people into two groups (corresponding to the two colors) such that no two people who dislike each other are in the same group.

Previous: Connected Components Pattern Next: Practice Problems

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Bipartite Graph Pattern

What is a Bipartite Graph?

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in the first set to a vertex in the second set.

In other words, a graph is bipartite if its vertices can be colored using two colors such that no adjacent vertices have the same color.

Problem Statement

Given an undirected graph, determine if it is bipartite.

Example 1:

Graph: 0 -- 1 -- 2 -- 3 -- 0

Is bipartite: true
(Color 0 and 2 with one color, 1 and 3 with another color)

Example 2:

Graph: 0 -- 1 -- 2 -- 0

Is bipartite: false
(Cannot color the vertices with two colors)

BFS Approach

Initialize a colors array with all vertices uncolored (-1)
For each uncolored vertex in the graph:
- Start BFS from this vertex and color it with color 0
- For each neighbor, color it with the opposite color of its parent
- If a neighbor is already colored with the same color as its parent, the graph is not bipartite
If all vertices can be colored properly, the graph is bipartite

Implementation

Here's an implementation of the bipartite graph checking algorithm using BFS:

Time and Space Complexity

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.

Related Problem: Possible Bipartition

Previous Next

Pattern 4: Bipartite Graph

Learn how to use BFS to check if a graph is bipartite by coloring its vertices with two colors.

What is a Bipartite Graph?

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in the first set to a vertex in the second set.

In other words, a graph is bipartite if its vertices can be colored using two colors such that no adjacent vertices have the same color.

Examples:

Bipartite Graph:
0 -- 1 -- 2 -- 3 -- 0

Coloring: Color 0 and 2 with one color, 1 and 3 with another color.

Explanation: We can divide the vertices into two sets {0, 2} and {1, 3} such that all edges connect vertices from different sets.

Non-Bipartite Graph:
0 -- 1 -- 2 -- 0

Not Bipartite: Cannot color the vertices with two colors.

Properties and Applications

Key Properties

A graph is bipartite if and only if it does not contain an odd-length cycle
All trees are bipartite
A complete bipartite graph is a bipartite graph where every vertex in the first set is connected to every vertex in the second set

Real-world Applications

Matching problems (e.g., job assignments, student-teacher pairings)
Network flow problems
Scheduling problems (e.g., assigning tasks to processors)
Social network analysis (e.g., dividing people into two groups with no conflicts)

The BFS Approach for Checking Bipartiteness

1Initialize

Initialize a colors array with all vertices uncolored (-1). We'll use two colors (0 and 1) to color the vertices.

2Start BFS

For each uncolored vertex, start BFS from it and color it with color 0. This handles disconnected graphs.

3Color Neighbors

For each neighbor of the current vertex, color it with the opposite color (1 - current color). If it's already colored, check for conflicts.

4Check Conflicts

If a neighbor is already colored with the same color as the current vertex, the graph is not bipartite. Otherwise, continue BFS.

Implementation

Here's an implementation of the bipartite graph checking algorithm using BFS:

isBipartite.js

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function isBipartite(graph) {
  const n = graph.length;
 
  // Initialize colors array with -1 (uncolored)
  const colors = Array(n).fill(-1);
 
  // Try to color the graph starting from each uncolored vertex
  for (let i = 0; i < n; i++) {
    // If this vertex is uncolored and we can't color it properly
    if (colors[i] === -1 && !bfsColorGraph(graph, i, colors)) {
      return false;
    }
  }
 
  // If we can color all vertices properly, the graph is bipartite
  return true;
}
 
function bfsColorGraph(graph, start, colors) {
  // Queue for BFS
  const queue = [start];
 
  // Color the start vertex with color 0
  colors[start] = 0;
 
  // While there are vertices in the queue
  while (queue.length > 0) {
    // Dequeue a vertex from the queue
    const current = queue.shift();
 
    // Get all adjacent vertices of the dequeued vertex
    for (const neighbor of graph[current]) {
      // If this adjacent vertex is uncolored
      if (colors[neighbor] === -1) {
        // Color it with the opposite color of the current vertex
        colors[neighbor] = 1 - colors[current];
        queue.push(neighbor);
      }
      // If this adjacent vertex is already colored with the same color as the current vertex
      else if (colors[neighbor] === colors[current]) {
        // The graph is not bipartite
        return false;
      }
    }
  }
 
  // If we can color all vertices properly, this component is bipartite
  return true;
}
 
// Example usage:
const graph1 = [
  [1, 3],  // Vertex 0 is connected to vertices 1 and 3
  [0, 2],  // Vertex 1 is connected to vertices 0 and 2
  [1, 3],  // Vertex 2 is connected to vertices 1 and 3
  [0, 2]   // Vertex 3 is connected to vertices 0 and 2
];
 
const graph2 = [
  [1, 2, 3],  // Vertex 0 is connected to vertices 1, 2, and 3
  [0, 2],     // Vertex 1 is connected to vertices 0 and 2
  [0, 1, 3],  // Vertex 2 is connected to vertices 0, 1, and 3
  [0, 2]      // Vertex 3 is connected to vertices 0 and 2
];
 
console.log(isBipartite(graph1)); // Output: true
console.log(isBipartite(graph2)); // Output: false

Time and Space Complexity

Time Complexity

O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Explanation: We visit each vertex once (O(V)) and explore each edge once (O(E)). Even though we run BFS multiple times, each vertex and edge is processed exactly once across all BFS calls.

Space Complexity

O(V), where V is the number of vertices in the graph.

Explanation: We need to store the colors array (O(V)) and the queue for BFS (O(V) in the worst case). Overall, the space complexity is O(V).

Common Pitfalls and Edge Cases

Disconnected Graphs

Make sure to check all components of the graph by running BFS from each uncolored vertex. A graph is bipartite only if all its components are bipartite.

Self-loops

A graph with self-loops (edges from a vertex to itself) cannot be bipartite because a vertex cannot be colored with two different colors.

Empty Graphs

An empty graph (no vertices) or a graph with no edges is trivially bipartite because there are no constraints on the coloring.

Related Problem: Possible Bipartition

possibleBipartition.js

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
function possibleBipartition(n, dislikes) {
  // Build the graph
  const graph = Array(n + 1).fill().map(() => []);
 
  for (const [a, b] of dislikes) {
    graph[a].push(b);
    graph[b].push(a);
  }
 
  // Initialize colors array with -1 (uncolored)
  const colors = Array(n + 1).fill(-1);
 
  // Try to color the graph starting from each uncolored vertex
  for (let i = 1; i <= n; i++) {
    // If this vertex is uncolored and we can't color it properly
    if (colors[i] === -1 && !bfsColorGraph(graph, i, colors)) {
      return false;
    }
  }
 
  // If we can color all vertices properly, the graph is bipartite
  return true;
}
 
function bfsColorGraph(graph, start, colors) {
  // Queue for BFS
  const queue = [start];
 
  // Color the start vertex with color 0
  colors[start] = 0;
 
  // While there are vertices in the queue
  while (queue.length > 0) {
    // Dequeue a vertex from the queue
    const current = queue.shift();
 
    // Get all adjacent vertices of the dequeued vertex
    for (const neighbor of graph[current]) {
      // If this adjacent vertex is uncolored
      if (colors[neighbor] === -1) {
        // Color it with the opposite color of the current vertex
        colors[neighbor] = 1 - colors[current];
        queue.push(neighbor);
      }
      // If this adjacent vertex is already colored with the same color as the current vertex
      else if (colors[neighbor] === colors[current]) {
        // The graph is not bipartite
        return false;
      }
    }
  }
 
  // If we can color all vertices properly, this component is bipartite
  return true;
}
 
// Example usage:
const n = 4;
const dislikes = [[1, 2], [1, 3], [2, 4], [3, 4]];
 
console.log(possibleBipartition(n, dislikes)); // Output: true

Previous: Connected Components Pattern Next: Practice Problems