Bipartite Graph Check in DSA Javascript - Execution Trace

Concept Flow - Bipartite Graph Check

Start with graph

↓

Pick unvisited node

↓

Assign color 0

↓

Use BFS/DFS to visit neighbors

↓

If neighbor uncolored -> assign opposite color

↓

If neighbor colored same as current -> Not Bipartite

↓

Repeat for all nodes

↓

If no conflicts -> Graph is Bipartite

We start from each unvisited node, assign a color, then use BFS or DFS to color neighbors with opposite colors. If a conflict arises, graph is not bipartite.

Execution Sample

DSA Javascript

function isBipartite(graph) {
  const color = Array(graph.length).fill(-1);
  for (let i = 0; i < graph.length; i++) {
    if (color[i] === -1) {
      if (!bfsCheck(i, graph, color)) return false;
    }
  }
  return true;
}

function bfsCheck(start, graph, color) {
  const queue = [start];
  color[start] = 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;
}

This code checks if a graph is bipartite by coloring nodes using BFS and verifying no two adjacent nodes share the same color.

Execution Table

Step	Operation	Current Node	Neighbor Node	Color Array	Conflict Detected	Visual State
1	Start BFS from node 0	0	-	[-1, -1, -1, -1]	No	0(0) - 1(-1) - 2(-1) - 3(-1)
2	Color node 0 with 0	0	-	[0, -1, -1, -1]	No	0(0) - 1(-1) - 2(-1) - 3(-1)
3	Visit neighbor 1 of node 0	0	1	[0, -1, -1, -1]	No	0(0) - 1(-1) - 2(-1) - 3(-1)
4	Color neighbor 1 with 1	1	-	[0, 1, -1, -1]	No	0(0) - 1(1) - 2(-1) - 3(-1)
5	Visit neighbor 3 of node 0	0	3	[0, 1, -1, -1]	No	0(0) - 1(1) - 2(-1) - 3(-1)
6	Color neighbor 3 with 1	3	-	[0, 1, -1, 1]	No	0(0) - 1(1) - 2(-1) - 3(1)
7	Visit neighbor 0 of node 1	1	0	[0, 1, -1, 1]	No	0(0) - 1(1) - 2(-1) - 3(1)
8	Visit neighbor 2 of node 1	1	2	[0, 1, -1, 1]	No	0(0) - 1(1) - 2(-1) - 3(1)
9	Color neighbor 2 with 0	2	-	[0, 1, 0, 1]	No	0(0) - 1(1) - 2(0) - 3(1)
10	Visit neighbor 1 of node 2	2	1	[0, 1, 0, 1]	No	0(0) - 1(1) - 2(0) - 3(1)
11	Visit neighbor 3 of node 2	2	3	[0, 1, 0, 1]	No	0(0) - 1(1) - 2(0) - 3(1)
12	Neighbor 3 color 1 differs from node 2 color 0	2	3	[0, 1, 0, 1]	No	0(0) - 1(1) - 2(0) - 3(1)
13	All nodes visited, no conflicts	-	-	[0, 1, 0, 1]	No	Graph is Bipartite

💡 All nodes colored without conflict, graph is bipartite.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	Final
color	[-1, -1, -1, -1]	[0, -1, -1, -1]	[0, 1, -1, -1]	[0, 1, -1, 1]	[0, 1, 0, 1]	[0, 1, 0, 1]
currentNode	-	0	1	3	2	-
conflictDetected	No	No	No	No	No	No

Key Moments - 3 Insights

Why do we assign colors as 0 and 1 instead of other numbers?

Colors 0 and 1 represent two groups. Assigning opposite colors to neighbors helps check if graph can be split into two sets without edges inside the same set. See execution_table steps 2,4,6 where colors alternate.

What happens if a neighbor already has the same color as current node?

This means the graph is not bipartite because two connected nodes share the same group. The algorithm detects this conflict and stops. In the execution_table, no conflict occurs, but if it did, conflictDetected would be 'Yes'.

Why do we start BFS from every unvisited node?

Graph can be disconnected. Starting BFS from each unvisited node ensures all parts are checked. See execution_table step 1 where BFS starts from node 0, and the loop in code covers all nodes.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the color assigned to node 1?

A 0

B -1

C 1

D 2

💡 Hint

Check the 'Color Array' column at step 4 in execution_table.

At which step does node 2 get colored?

A Step 9

B Step 6

C Step 3

D Step 12

💡 Hint

Look for the step where color array changes to include node 2's color.

If neighbor 3 had the same color as node 2 at step 12, what would happen?

A Algorithm continues normally

B Conflict detected, graph not bipartite

C Node 3 color changes automatically

D Node 2 color changes automatically

💡 Hint

Refer to the 'Conflict Detected' column and explanation in key_moments about color conflicts.

Concept Snapshot

Bipartite Graph Check:
- Use BFS/DFS to color nodes with 0 or 1
- Assign opposite color to neighbors
- If neighbor has same color, graph is not bipartite
- Check all connected components
- Return true if no conflicts found

Full Transcript

To check if a graph is bipartite, we assign colors 0 and 1 to nodes so that no two connected nodes share the same color. We start from each unvisited node, color it 0, then use BFS to color neighbors with the opposite color. If we find a neighbor with the same color, the graph is not bipartite. We repeat this for all nodes to cover disconnected parts. The example shows step-by-step coloring and checking, ending with a successful bipartite confirmation.

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