Bipartite Graph Check in DSA Javascript - Time & Space Complexity

Time Complexity: Bipartite Graph Check

O(V + E)

Understanding Time Complexity

Checking if a graph is bipartite means deciding if we can split nodes into two groups without edges inside the same group.

We want to know how the time needed grows as the graph gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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;
}
    

This code uses a breadth-first search to color nodes and check if the graph can be split into two groups without conflicts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop with queue processes each node and its neighbors once.
• How many times: Each node is visited once, and each edge is checked once or twice depending on direction.

How Execution Grows With Input

As the number of nodes and edges grows, the time to check colors grows roughly with the total nodes plus edges.

Input Size (n)	Approx. Operations
10 nodes, 15 edges	About 25 operations (visiting nodes and edges)
100 nodes, 200 edges	About 300 operations
1000 nodes, 3000 edges	About 4000 operations

Pattern observation: Operations grow roughly in a straight line with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(V + E)

This means the time grows linearly with the number of nodes plus the number of edges in the graph.

Common Mistake

[X] Wrong: "The time depends only on the number of nodes, not edges."

[OK] Correct: Checking neighbors means looking at edges too, so edges affect the time as much as nodes.

Interview Connect

Understanding this time complexity helps you explain how graph traversal works efficiently and shows you can analyze real problems involving networks or connections.

Self-Check

"What if we used depth-first search (DFS) instead of breadth-first search (BFS)? How would the time complexity change?"

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