Bipartite Graph Check in DSA Typescript

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 -> 5
Group B: 2 -> 4 -> 6
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 this graph can be divided into two groups with no edges inside the same group

Step 1: Start coloring node 1 with color 0

Node colors: [1:0, 2:null, 3:null, 4:null]

Why: We pick a color for the first node to start the grouping

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

Node colors: [1:0, 2:1, 3:null, 4:1]

Why: Neighbors must have opposite color to avoid same-group edges

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

Node colors: [1:0, 2:1, 3:0, 4:1]

Why: Neighbors of node 2 get opposite color to 2

Step 4: Check neighbors of 3 (nodes 2 and 4) for color conflicts

Node colors: [1:0, 2:1, 3:0, 4:1]

Why: Neighbors have opposite colors, no conflict found

Step 5: Check neighbors of 4 (nodes 1 and 3) for color conflicts

Node colors: [1:0, 2:1, 3:0, 4:1]

Why: Neighbors have opposite colors, no conflict found

Result:

Node colors: [1:0, 2:1, 3:0, 4:1] -> Graph is bipartite

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;

  constructor(edges: [number, number][]) {
    this.adjacencyList = new Map();
    for (const [u, v] of edges) {
      if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
      if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
      this.adjacencyList.get(u)!.push(v);
      this.adjacencyList.get(v)!.push(u);
    }
  }

  isBipartite(): boolean {
    const color = new Map<number, number>();

    for (const node of this.adjacencyList.keys()) {
      if (!color.has(node)) {
        if (!this.dfsCheck(node, color, 0)) return false;
      }
    }
    return true;
  }

  private dfsCheck(node: number, color: Map<number, number>, c: number): boolean {
    color.set(node, c); // assign color to current node

    for (const neighbor of this.adjacencyList.get(node)!) {
      if (!color.has(neighbor)) {
        if (!this.dfsCheck(neighbor, color, 1 - c)) return false; // assign opposite color
      } else if (color.get(neighbor) === c) {
        return false; // neighbor has same color, not bipartite
      }
    }
    return true;
  }
}

// Driver code
const edges: [number, number][] = [[1, 2], [2, 3], [3, 4], [4, 1]];
const graph = new Graph(edges);
console.log(graph.isBipartite() ? "Graph is bipartite" : "Graph is not bipartite");

color.set(node, c); // assign color to current node

assign color to current node to mark its group

for (const neighbor of this.adjacencyList.get(node)!) {

check all neighbors of current node

if (!color.has(neighbor)) {

if neighbor not colored, assign opposite color recursively

if (!this.dfsCheck(neighbor, color, 1 - c)) return false; // assign opposite color

recursive call to color neighbor with opposite color

else if (color.get(neighbor) === c) {

if neighbor has same color, graph is not bipartite

Output

Graph is bipartite

Complexity Analysis

Time: O(V + E) because we visit every node and edge once during DFS

Space: O(V) for storing colors and recursion stack in worst case

vs Alternative: Compared to BFS approach, DFS uses recursion but both have same time and space complexity

Edge Cases

Empty graph

Returns true since no edges mean no conflicts

DSA Typescript

for (const node of this.adjacencyList.keys()) { if (!color.has(node)) { ... } }

Graph with one node and no edges

Returns true as single node can be colored any color

DSA Typescript

color.set(node, c); // assign color to current node

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

Returns false because odd cycle cannot be bipartite

DSA Typescript

else if (color.get(neighbor) === c) { return false; }

When to Use This Pattern

When a problem asks if nodes can be split into two groups with no internal edges, use bipartite check with graph coloring to detect conflicts.

Common Mistakes

Mistake: Not checking all connected components, missing disconnected nodes
Fix: Loop over all nodes and run DFS/BFS if not colored yet

Mistake: Assigning same color to neighbors instead of opposite
Fix: Assign opposite color using 1 - current color

Summary

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

Use when you need to separate nodes into two sets without internal connections.

The key is to color nodes alternately and detect any color conflicts.

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