Bipartite Graph Check in DSA Javascript - Build from Scratch

Bipartite Graph Check

📖 Scenario: You are working on a social networking app. You want to check if the users can be split into two groups so that no two friends are in the same group. This means the friendship connections form a bipartite graph.

🎯 Goal: Build a program that checks if a given graph is bipartite using JavaScript. You will represent the graph as an adjacency list and use a coloring method to verify the bipartite property.

📋 What You'll Learn

Create a graph as an adjacency list with exact nodes and edges

Create a color array to track node colors

Implement a function to check bipartite property using BFS

Print the result as true or false

💡 Why This Matters

🌍 Real World

Bipartite graph checks are useful in social networks, scheduling problems, and matching algorithms where two groups must be separated without conflicts.

💼 Career

Understanding graph traversal and bipartite checks is important for software engineers working on network analysis, recommendation systems, and optimization problems.

1

Create the graph adjacency list

Create a constant called graph as an adjacency list with these exact entries: 0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]

DSA Javascript

# Your code here

Hint

Use an object where keys are node numbers and values are arrays of connected nodes.

2

Create the color array

Create a variable called color as an array of length 4 filled with -1 to represent uncolored nodes

DSA Javascript

const graph = {
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
};

// Your code here

Hint

Use new Array(4).fill(-1) to create an array with 4 elements all set to -1.

3

Implement the bipartite check function

Write a function called isBipartite that takes graph and color as parameters. Use a for loop with variable node from 0 to 3. If color[node] is -1, assign color[node] = 0 and use a queue to perform BFS. Inside BFS, for each neighbor, if color[neighbor] is -1, assign it the opposite color. If color[neighbor] equals color[current], return false. After the loop, return true.

DSA Javascript

const graph = {
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
};

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

// Your code here

Hint

Use BFS with a queue to assign colors and check for conflicts.

4

Print the bipartite check result

Write a console.log statement to print the result of calling isBipartite(graph, color)

DSA Javascript

const graph = {
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
};

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

function isBipartite(graph, color) {
  for (let node = 0; node  0) {
        const current = queue.shift();
        for (const neighbor of graph[current]) {
          if (color[neighbor] === -1) {
            color[neighbor] = 1 - color[current];
            queue.push(neighbor);
          } else if (color[neighbor] === color[current]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

// Your code here

Hint

Call the function and print the result using console.log.

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