Bipartite Graph Check in DSA Typescript - Execution Trace

Concept Flow - Bipartite Graph Check

Start with uncolored graph

↓

Pick an unvisited node

↓

Assign color 0

↓

Use BFS/DFS to visit neighbors

↓

If neighbor uncolored, assign opposite color

↓

If neighbor colored same as current, stop: Not Bipartite

↓

Repeat for all nodes

↓

If no conflicts, graph is Bipartite

We color nodes using two colors while traversing. If a conflict arises, graph is not bipartite.

Execution Sample

DSA Typescript

function isBipartite(graph: number[][]): boolean {
  const color = new 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: number, graph: number[][], color: number[]): boolean {
  const queue: number[] = [start];
  color[start] = 0;
  while (queue.length > 0) {
    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;
}

Checks if graph is bipartite by coloring nodes using BFS.

Execution Table

Step	Operation	Current Node	Neighbor	Color Array	Conflict Detected	Visual State
1	Start BFS from node 0	0	-	[-1, -1, -1, -1]	No	[0(-), 1(-), 2(-), 3(-)]
2	Color node 0 with 0	0	-	[0, -1, -1, -1]	No	[0(0), 1(-), 2(-), 3(-)]
3	Visit neighbor 1 of node 0	0	1	[0, -1, -1, -1]	No	[0(0), 1(-), 2(-), 3(-)]
4	Color neighbor 1 with 1	1	-	[0, 1, -1, -1]	No	[0(0), 1(1), 2(-), 3(-)]
5	Visit neighbor 3 of node 0	0	3	[0, 1, -1, -1]	No	[0(0), 1(1), 2(-), 3(-)]
6	Color neighbor 3 with 1	3	-	[0, 1, -1, 1]	No	[0(0), 1(1), 2(-), 3(1)]
7	Visit neighbor 0 of node 1	1	0	[0, 1, -1, 1]	No	[0(0), 1(1), 2(-), 3(1)]
8	Neighbor 0 already colored 0 (opposite), continue	1	0	[0, 1, -1, 1]	No	[0(0), 1(1), 2(-), 3(1)]
9	Visit neighbor 2 of node 1	1	2	[0, 1, -1, 1]	No	[0(0), 1(1), 2(-), 3(1)]
10	Color neighbor 2 with 0	2	-	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
11	Visit neighbor 1 of node 2	2	1	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
12	Neighbor 1 already colored 1 (opposite), continue	2	1	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
13	Visit neighbor 3 of node 2	2	3	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
14	Neighbor 3 already colored 1 (opposite), continue	2	3	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
15	Visit neighbor 0 of node 3	3	0	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
16	Neighbor 0 already colored 0 (opposite), continue	3	0	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
17	Visit neighbor 2 of node 3	3	2	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
18	Neighbor 2 already colored 0 (opposite), continue	3	2	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]
19	All nodes visited, no conflict	-	-	[0, 1, 0, 1]	No	[0(0), 1(1), 2(0), 3(1)]

💡 All nodes colored without conflict, graph is bipartite

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 10	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 only when a node is uncolored?

Because if a node is already colored, it means it was visited before and assigned a color. Reassigning could cause conflicts. See steps 7 and 11 where neighbors already have colors and no reassignment happens.

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

This means the graph is not bipartite because two connected nodes share the same color. The algorithm stops immediately. In this example, no such conflict occurs, but if it did, the 'Conflict Detected' column would show 'Yes'.

Why do we start BFS from every unvisited node?

Because the graph can be disconnected. We must check each component separately. In this example, the graph is connected, so BFS starts only once at node 0.

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 (uncolored)

D 2

💡 Hint

Check the 'Color Array' column at Step 4 in the execution table.

At which step does node 2 get its color assigned?

A Step 10

B Step 6

C Step 14

D Step 2

💡 Hint

Look for the step where 'Color neighbor 2 with 0' happens in the 'Operation' column.

If node 3 was colored 0 instead of 1 at Step 6, what would happen?

A No conflict, graph still bipartite

B Conflict detected later, graph not bipartite

C Algorithm would skip node 3

D Color array would remain unchanged

💡 Hint

Refer to the 'Conflict Detected' column and the rule that neighbors must have opposite colors.

Concept Snapshot

Bipartite Graph Check:
- Use two colors (e.g., 0 and 1) to color nodes.
- Traverse graph using BFS or DFS.
- Assign opposite color to neighbors.
- If a neighbor has same color, graph is not bipartite.
- Check all components for disconnected graphs.

Full Transcript

This visualization shows how to check if a graph is bipartite by coloring nodes with two colors during a BFS traversal. We start with all nodes uncolored (-1). We pick an unvisited node, color it 0, then color its neighbors 1, their neighbors 0, and so on. If at any point a neighbor has the same color as the current node, the graph is not bipartite. The execution table tracks each step, the current node, neighbors, color assignments, and conflicts. The variable tracker shows how the color array changes over time. Key moments clarify why colors are assigned only once, what conflicts mean, and why BFS starts at every unvisited node. The quiz tests understanding of color assignments and conflict detection. The snapshot summarizes the process in simple steps.

Practice

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

easy

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

B. It has an equal number of vertices and edges

C. It contains at least one cycle

D. All vertices have the same degree

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph 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.

3. Final Answer:

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

4. Quick Check:

   Bipartite = Two groups, 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 TypeScript data structure is best to represent a graph for bipartite check?

easy

A. Adjacency list using Map

B. Array of numbers

C. String array

D. Single number variable

Solution

1. Step 1: Identify graph representation needs

   We need to store edges for each vertex efficiently to check bipartite property.

2. Step 2: Choose suitable data structure

   An adjacency list using Map stores neighbors for each vertex clearly and is efficient.

3. Final Answer:

   Adjacency list using Map<number, number[]> -> Option A

4. Quick Check:

   Graph as adjacency list = Map [OK]

Hint: Use adjacency list (Map) for graph edges [OK]

Common Mistakes:

• Using simple arrays without edge info
• Using strings which don't represent graph
• Using single variable instead of structure

3. What is the output of this TypeScript code that checks if a graph is bipartite?

const graph = new Map([
  [0, [1, 3]],
  [1, [0, 2]],
  [2, [1, 3]],
  [3, [0, 2]]
]);

function isBipartite(graph: Map): boolean {
  const color = new Map();
  for (const node of graph.keys()) {
    if (!color.has(node)) {
      const queue = [node];
      color.set(node, 0);
      while (queue.length) {
        const u = queue.shift()!;
        for (const v of graph.get(u)!) {
          if (!color.has(v)) {
            color.set(v, 1 - color.get(u)!);
            queue.push(v);
          } else if (color.get(v) === color.get(u)) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

console.log(isBipartite(graph));

medium

A. false

B. true

C. undefined

D. SyntaxError

Solution

1. Step 1: Analyze graph structure

   The graph is a square cycle: 0-1-2-3-0, which is an even cycle and bipartite.

2. Step 2: Trace BFS coloring

   Starting from node 0 with color 0, neighbors get color 1, their neighbors color 0, no conflicts found.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Even cycle graph is bipartite = true [OK]

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

Common Mistakes:

• Assuming all cycles are not bipartite
• Confusing color assignment logic
• Missing BFS queue processing

4. Find the bug in this TypeScript function that checks if a graph is bipartite:

function isBipartite(graph: Map): boolean {
  const color = new Map();
  for (const node of graph.keys()) {
    if (!color.has(node)) {
      const queue = [node];
      color.set(node, 0);
      while (queue.length) {
        const u = queue.shift()!;
        for (const v of graph.get(u)!) {
          if (!color.has(v)) {
            color.set(v, color.get(u)!);
            queue.push(v);
          } else if (color.get(v) === color.get(u)) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

medium

A. Missing return type boolean

B. queue.shift()! should be queue.pop()

C. color.set(v, color.get(u)!) should be color.set(v, 1 - color.get(u)!)

D. graph.get(u)! should be graph.get(v)!

Solution

1. Step 1: Identify color assignment error

   The code assigns the same color to neighbors, which breaks bipartite logic.

2. Step 2: Correct color assignment

   Neighbors must get opposite color: 1 - color of current node.

3. Final Answer:

   color.set(v, 1 - color.get(u)!) -> Option C

4. Quick Check:

   Neighbor color = opposite of current [OK]

Hint: Neighbors must have opposite colors [OK]

Common Mistakes:

• Assigning same color to neighbors
• Using pop instead of shift in BFS
• Incorrect graph access

5. Given a graph represented as adjacency list:

const graph = new Map([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 3]],
  [3, [1, 2, 4]],
  [4, [3]]
]);

Is this graph bipartite? Choose the correct reasoning.

hard

A. Yes, because it has no odd-length cycles

B. No, because node 3 connects to nodes in the same set

C. Yes, because all nodes have even degree

D. No, because it contains a triangle (3-cycle)

Solution

1. Step 1: Identify cycles in the graph

   There is a triangle cycle: nodes 1-3-2-1 (edges 1-3, 3-2, 2-1), which is an odd-length cycle.

2. Step 2: Recall bipartite property about cycles

   Graphs containing odd-length cycles are not bipartite.

3. Final Answer:

   No, because it contains a triangle (3-cycle) -> Option D

4. Quick Check:

   Odd cycle present = not bipartite [OK]

Hint: Odd cycles mean graph is not bipartite [OK]

Common Mistakes:

• Falsely identifying triangle in 1-2-3 (actually 1-3-2 forms triangle)
• Assuming even degree means bipartite
• Confusing connectivity with bipartite property