Bipartite Graph Check in DSA Javascript

Mental Model

A bipartite graph can be split into two groups where no nodes inside the same group connect to each other.

Analogy: Imagine two teams playing a game where players only pass the ball to the other team, never to their own team members.

Group A: 1 -> 3 -> null
Group B: 2 -> 4 -> null
Edges only go between groups, never inside one group.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-4, 4-1

Goal: Check if the graph can be divided into two groups with no edges inside the same group

Step 1: Start coloring node 1 with color 0

Colors: {1:0, 2:null, 3:null, 4:null}

Why: We pick a starting node and assign it a group color

Step 2: Color neighbors of 1 with color 1 (node 2 and node 4)

Colors: {1:0, 2:1, 3:null, 4:1}

Why: Neighbors must be in the opposite group

Step 3: Color neighbors of 2 with color 0 (node 3)

Colors: {1:0, 2:1, 3:0, 4:1}

Why: Neighbors of node 2 must be opposite color

Step 4: Check neighbors of 3: node 4 already colored 1, no conflict

Colors: {1:0, 2:1, 3:0, 4:1}

Why: No same color neighbors means graph is bipartite so far

Step 5: All nodes colored without conflict, graph is bipartite

Colors: {1:0, 2:1, 3:0, 4:1}

Why: Successful coloring proves bipartite property

Result:

Colors: {1:0, 2:1, 3:0, 4:1} -> Graph is bipartite

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Array(vertices + 1).fill(null).map(() => []);
  }

  addEdge(u, v) {
    this.adj[u].push(v);
    this.adj[v].push(u);
  }

  isBipartite() {
    const color = new Array(this.V + 1).fill(-1);

    for (let start = 1; start <= this.V; start++) {
      if (color[start] === -1) {
        color[start] = 0; // assign first color
        const queue = [start];

        while (queue.length > 0) {
          const u = queue.shift();

          for (const v of this.adj[u]) {
            if (color[v] === -1) {
              color[v] = 1 - color[u]; // assign opposite color
              queue.push(v);
            } else if (color[v] === color[u]) {
              return false; // same color neighbor found
            }
          }
        }
      }
    }
    return true;
  }
}

// Driver code
const g = new Graph(4);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 1);

if (g.isBipartite()) {
  console.log("Graph is bipartite");
} else {
  console.log("Graph is NOT bipartite");
}

color[start] = 0; // assign first color

start coloring the first uncolored node with color 0

const queue = [start];

initialize queue for BFS traversal

const u = queue.shift();

dequeue current node to process its neighbors

if (color[v] === -1) { color[v] = 1 - color[u]; queue.push(v); }

assign opposite color to uncolored neighbor and enqueue it

else if (color[v] === color[u]) { return false; }

if neighbor has same color, graph is not bipartite

Output

Graph is bipartite

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during BFS

Space: O(V) for the color array and BFS queue

vs Alternative: Naive approach tries all partitions which is exponential; BFS coloring is efficient and linear

Edge Cases

Empty graph (no vertices)

Returns true since no edges exist to violate bipartite property

DSA Javascript

for (let start = 1; start <= this.V; start++) { if (color[start] === -1) {

Graph with one vertex and no edges

Returns true, single node can be colored any color

DSA Javascript

color[start] = 0; // assign first color

Graph with odd cycle (e.g., triangle 1-2-3-1)

Returns false because coloring fails due to same color neighbors

DSA Javascript

else if (color[v] === color[u]) { return false; }

When to Use This Pattern

When you need to check if a graph can be split into two groups with no edges inside a group, use BFS coloring to detect bipartite property efficiently.

Common Mistakes

Mistake: Not checking all disconnected components of the graph
Fix: Use a loop over all vertices to start BFS if uncolored

Mistake: Assigning the same color to neighbors instead of opposite color
Fix: Assign neighbor color as 1 - current node color

Summary

Checks if a graph can be divided into two groups with no edges inside the same group.

Use when you want to verify if a graph is bipartite or to solve problems involving two-coloring.

The key insight is to color nodes using two colors and check for conflicts during BFS traversal.

Practice

1. What does it mean if a graph is bipartite?

easy

A. All vertices have the same degree

B. It has an equal number of vertices and edges

C. It contains at least one cycle

D. Its vertices can be divided into two groups with no edges inside the same group

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph means vertices can be split into two sets where no edges connect vertices within the same set.

2. Step 2: Compare options with definition

   Only Its vertices can be divided into two groups with no edges inside the same group matches this definition exactly. Other options describe unrelated properties.

3. Final Answer:

   Its vertices can be divided into two groups with no edges inside the same group -> Option D

4. Quick Check:

   Bipartite graph = vertices split into two groups with no internal edges [OK]

Hint: Bipartite means two groups with no edges inside groups [OK]

Common Mistakes:

• Confusing bipartite with equal vertices and edges
• Thinking bipartite means no cycles
• Assuming all vertices have same degree

2. Which of the following is the correct way to initialize a color array for bipartite check in JavaScript?

easy

A. const color = new Array(n).fill(-1);

B. const color = Array(n).map();

C. const color = new Array(n).map();

D. const color = Array.fill(n, -1);

Solution

1. Step 1: Understand array initialization with fill

   To create an array of length n filled with -1, use new Array(n).fill(-1).

2. Step 2: Check each option for correctness

   Options A and B call map without a callback function, causing TypeError. const color = Array.fill(n, -1); uses non-existent Array.fill static method. Only C uses correct syntax.

3. Final Answer:

   const color = new Array(n).fill(-1); -> Option A

4. Quick Check:

   Use new Array(n).fill(value) to initialize array [OK]

Hint: Use new Array(n).fill(value) to initialize arrays [OK]

Common Mistakes:

• Calling map without callback function
• Wrong syntax for fill method
• Confusing Array.fill with fill method

3. What will be the output of the following code snippet?

const graph = [[1,3],[0,2],[1,3],[0,2]];
function isBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(-1);
  for (let i = 0; i < n; i++) {
    if (color[i] === -1) {
      const queue = [i];
      color[i] = 0;
      while (queue.length) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
          if (color[neighbor] === -1) {
            color[neighbor] = 1 - color[node];
            queue.push(neighbor);
          } else if (color[neighbor] === color[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}
console.log(isBipartite(graph));

medium

A. undefined

B. false

C. true

D. TypeError

Solution

1. Step 1: Analyze graph structure and BFS coloring

   The graph is a square cycle: 0-1-2-3-0. The BFS colors nodes alternately. Since it's an even cycle, it is bipartite.

2. Step 2: Check BFS color assignment and conflict detection

   No two adjacent nodes have the same color, so the function returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Even cycle graph is bipartite = true [OK]

Hint: Even length cycles are bipartite, odd cycles are not [OK]

Common Mistakes:

• Assuming all cycles are not bipartite
• Confusing color assignment logic
• Forgetting to check all connected components

4. Identify the bug in this bipartite check code snippet:

function checkBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(-1);
  for (let i = 0; i < n; i++) {
    if (color[i] === -1) {
      const stack = [i];
      color[i] = 0;
      while (stack.length) {
        const node = stack.pop();
        for (const neighbor of graph[node]) {
          if (color[neighbor] === -1) {
            color[neighbor] = color[node];
            stack.push(neighbor);
          } else if (color[neighbor] === color[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

medium

A. stack should be replaced with queue for BFS

B. color[neighbor] should be set to 1 - color[node] instead of color[node]

C. color array should be initialized with 0 instead of -1

D. The function should return true inside the loop

Solution

1. Step 1: Review color assignment logic

   The code assigns color[neighbor] = color[node], which means neighbors get the same color, violating bipartite rules.

2. Step 2: Correct color assignment for bipartite check

   Neighbors must have opposite colors, so color[neighbor] = 1 - color[node] is correct.

3. Final Answer:

   color[neighbor] should be set to 1 - color[node] instead of color[node] -> Option B

4. Quick Check:

   Neighbors must have opposite colors [OK]

Hint: Neighbors get opposite color: 1 - current color [OK]

Common Mistakes:

• Assigning same color to neighbors
• Confusing stack and queue usage
• Wrong initial color array values

5. Given a graph represented as adjacency list:

const graph = [[1,2],[0,3],[0,3],[1,2,4],[3]];

Which of the following statements is true about this graph's bipartite property?

hard

A. The graph is bipartite because it contains no odd cycles

B. The graph is not bipartite because node 4 connects to node 3 only

C. The graph is bipartite because all nodes have even degree

D. The graph is not bipartite because it contains an odd cycle involving nodes 1, 3, and 4

Solution

1. Step 1: Identify cycles in the graph

   The graph edges are 0->1,2; 1->0,3; 2->0,3; 3->1,2,4; 4->3. Cycles like 0-1-3-2-0 are even length (4). No odd-length cycles.

2. Step 2: Understand bipartite condition with odd cycles

   Graphs without odd cycles are bipartite.

3. Final Answer:

   The graph is bipartite because it contains no odd cycles -> Option A

4. Quick Check:

   No odd cycles means bipartite [OK]

Hint: Odd cycles break bipartite property [OK]

Common Mistakes:

• Misidentifying paths like 1-3-4 as odd cycles
• Assuming single connections make it non-bipartite
• Confusing node degree with bipartite property