Bipartite Graph Check in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bipartite Check on Simple Graph

What is the output of the following JavaScript code that checks if a graph is bipartite?

DSA Javascript

function isBipartite(graph) {
  const n = graph.length;
  const colors = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    if (colors[i] === -1) {
      const queue = [i];
      colors[i] = 0;

      while (queue.length) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
          if (colors[neighbor] === -1) {
            colors[neighbor] = 1 - colors[node];
            queue.push(neighbor);
          } else if (colors[neighbor] === colors[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

const graph = [[1,3],[0,2],[1,3],[0,2]];
console.log(isBipartite(graph));

A undefined

B false

C true

D TypeError

💡 Hint

Think about whether the graph can be colored with two colors without conflicts.

The graph is a square (4 nodes connected in a cycle of length 4). Such a cycle with even length is bipartite. The function colors nodes alternately and finds no conflicts, so it returns true.

❓ Predict Output

intermediate

Output of Bipartite Check on Odd Cycle Graph

What is the output of this JavaScript code that checks if a graph with an odd cycle is bipartite?

DSA Javascript

function isBipartite(graph) {
  const n = graph.length;
  const colors = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    if (colors[i] === -1) {
      const queue = [i];
      colors[i] = 0;

      while (queue.length) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
          if (colors[neighbor] === -1) {
            colors[neighbor] = 1 - colors[node];
            queue.push(neighbor);
          } else if (colors[neighbor] === colors[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

const graph = [[1,2],[0,2],[0,1]];
console.log(isBipartite(graph));

A true

B false

C RangeError

D null

💡 Hint

Odd cycles cannot be bipartite.

The graph is a triangle (3 nodes all connected). Odd cycles are not bipartite because you cannot color nodes with two colors without conflict. The function detects this and returns false.

🧠 Conceptual

advanced

Why BFS is used in Bipartite Check?

Why is Breadth-First Search (BFS) commonly used to check if a graph is bipartite instead of Depth-First Search (DFS)?

A BFS colors nodes level by level, making it easier to detect conflicts between adjacent levels.

B DFS cannot be used to check bipartite property because it does not visit all nodes.

C DFS requires more memory than BFS, so BFS is preferred.

D BFS is faster than DFS in all graph algorithms.

💡 Hint

Think about how BFS explores nodes in layers.

BFS explores nodes level by level, which naturally fits the two-color assignment for bipartite checking. It helps detect conflicts between nodes in the same or adjacent levels easily.

❓ Predict Output

advanced

Output of Bipartite Check on Disconnected Graph

What is the output of this JavaScript code checking bipartite property on a disconnected graph?

DSA Javascript

function isBipartite(graph) {
  const n = graph.length;
  const colors = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    if (colors[i] === -1) {
      const queue = [i];
      colors[i] = 0;

      while (queue.length) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
          if (colors[neighbor] === -1) {
            colors[neighbor] = 1 - colors[node];
            queue.push(neighbor);
          } else if (colors[neighbor] === colors[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

const graph = [[1],[0],[]];
console.log(isBipartite(graph));

A ReferenceError

B false

C undefined

D true

💡 Hint

Disconnected graphs can still be bipartite if all components are bipartite.

The graph has two connected components: one edge between nodes 0 and 1, and node 2 isolated. Both components are bipartite, so the function returns true.

🧠 Conceptual

expert

Bipartite Graphs and Odd Cycles

Which statement correctly describes the relationship between bipartite graphs and cycles?

A A graph is bipartite if and only if it contains no odd-length cycles.

B A graph is bipartite if it contains at least one odd-length cycle.

C Bipartite graphs always contain odd-length cycles.

D The presence of even-length cycles makes a graph non-bipartite.

💡 Hint

Think about what odd cycles imply for two-coloring.

A graph is bipartite exactly when it has no cycles of odd length. Odd cycles prevent proper two-coloring, while even cycles do not.

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