Bipartite Graph Check in DSA Java

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 players on the other team, never to their own teammates.

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[-1], 3[-1], 4[-1]

Why: We assign the first color to start the grouping

Step 2: Color neighbors of node 1 with color 1

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

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

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

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

Why: Alternate color for neighbors to maintain bipartite property

Step 4: Check neighbor of node 3 (node 4) and verify color

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

Why: Node 4 already colored with opposite color, so no conflict

Step 5: Check neighbor of node 4 (node 1) and verify color

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

Why: Node 1 has opposite color, so graph is bipartite

Result:

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

Annotated Code

DSA Java

import java.util.*;

public class BipartiteGraphCheck {
    public static boolean isBipartite(List<List<Integer>> graph) {
        int n = graph.size();
        int[] colors = new int[n];
        Arrays.fill(colors, -1); // -1 means uncolored

        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                if (!bfsCheck(graph, i, colors)) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean bfsCheck(List<List<Integer>> graph, int start, int[] colors) {
        Queue<Integer> queue = new LinkedList<>();
        colors[start] = 0; // start coloring with 0
        queue.offer(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.get(node)) {
                if (colors[neighbor] == -1) {
                    colors[neighbor] = 1 - colors[node]; // alternate color
                    queue.offer(neighbor);
                } else if (colors[neighbor] == colors[node]) {
                    return false; // same color neighbor found, not bipartite
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // Graph: 1-2, 2-3, 3-4, 4-1 (0-based indexing: 0-1,1-2,2-3,3-0)
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(1);
        graph.get(1).add(0);
        graph.get(1).add(2);
        graph.get(2).add(1);
        graph.get(2).add(3);
        graph.get(3).add(2);
        graph.get(3).add(0);
        graph.get(0).add(3);

        boolean result = isBipartite(graph);
        System.out.println("Graph is bipartite: " + result);
    }
}

colors[start] = 0; // start coloring with 0

assign first color to start node

colors[neighbor] = 1 - colors[node]; // alternate color

assign opposite color to neighbor node

if (colors[neighbor] == colors[node]) { return false; }

detect conflict if neighbor has same color

for (int i = 0; i < n; i++) { if (colors[i] == -1) { ... } }

check all nodes to handle disconnected graph

Output

Graph is bipartite: true

Complexity Analysis

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

Space: O(V) for the colors array and BFS queue

vs Alternative: Compared to DFS, BFS is equally efficient here; naive checking all pairs would be O(V^2)

Edge Cases

Empty graph

Returns true since no edges mean no conflicts

DSA Java

for (int i = 0; i < n; i++) { if (colors[i] == -1) { ... } }

Graph with one node and no edges

Returns true as single node can be colored any color

DSA Java

colors[start] = 0; // start coloring with 0

Graph with odd cycle (e.g., triangle)

Returns false because odd cycle cannot be bipartite

DSA Java

if (colors[neighbor] == colors[node]) { return false; }

When to Use This Pattern

When you need to split nodes into two groups with no internal edges, use bipartite check with BFS or DFS coloring to detect conflicts.

Common Mistakes

Mistake: Not checking all disconnected components of the graph
Fix: Use a loop over all nodes and run BFS/DFS only on uncolored nodes

Mistake: Assigning the same color to neighbors
Fix: Always assign the opposite color to neighbors (1 - current color)

Summary

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

Use when you need to verify if a graph is bipartite, especially in problems involving two-coloring or grouping.

The key insight is to color nodes alternately and detect if a conflict arises when neighbors share the same color.

Practice

1. What does it mean for a graph to be bipartite?

easy

A. Its vertices can be divided into two sets with no edges inside the same set

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 is one where vertices can be split into two groups so that no edge connects vertices within the same group.

2. Step 2: Compare options with definition

   Only Its vertices can be divided into two sets with no edges inside the same set matches this definition exactly. Other options describe unrelated properties.

3. Final Answer:

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

4. Quick Check:

   Bipartite = Two sets, 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 Java code snippet correctly initializes a graph as an adjacency list for bipartite check?

easy

A. List graph = new ArrayList<>();

B. int graph = new int[5][5];

C. Map graph = new HashMap<>();

D. Set<Integer> graph = new HashSet<>();

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for a graph is usually a list of lists, where each inner list holds neighbors of a vertex.

2. Step 2: Match code snippets to adjacency list

   List<List<Integer>> graph = new ArrayList<>(); uses List of Lists, suitable for adjacency list. int graph = new int[5][5]; is a 2D array (adjacency matrix), not list. Options A and C use Set and Map, which are not standard adjacency lists.

3. Final Answer:

   List<List<Integer>> graph = new ArrayList<>(); -> Option A

4. Quick Check:

   Adjacency list = List of Lists [OK]

Hint: Adjacency list uses List of Lists in Java [OK]

Common Mistakes:

• Using 2D arrays instead of lists
• Using Map or Set incorrectly for adjacency
• Not initializing the list properly

3. What is the output of the following Java code snippet checking bipartite for a graph with edges: 0-1, 1-2, 2-3, 3-0?

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < 4; i++) graph.add(new ArrayList<>());
graph.get(0).add(1); graph.get(1).add(0);
graph.get(1).add(2); graph.get(2).add(1);
graph.get(2).add(3); graph.get(3).add(2);
graph.get(3).add(0); graph.get(0).add(3);

boolean result = isBipartite(graph);
System.out.println(result);

Assuming isBipartite correctly checks bipartite property.

medium

A. false

B. true

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze the graph structure

   The graph has edges forming a cycle of length 4: 0-1-2-3-0.

2. Step 2: Check bipartite condition for even cycle

   Even length cycles (4) are bipartite, so the graph should be bipartite. But the edges connect 0-3 and 3-2, forming a cycle of length 4.

3. Step 3: Re-examine edges carefully

   The cycle is 0-1-2-3-0, which is even length, so graph is bipartite. So output should be true.

4. Final Answer:

   true -> Option B

5. Quick Check:

   Even cycle graph is bipartite = true [OK]

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

Common Mistakes:

• Thinking all cycles are not bipartite
• Confusing cycle length parity
• Assuming runtime errors without cause

4. Identify the bug in this Java method for bipartite check:

boolean isBipartite(List<List<Integer>> graph) {
  int n = graph.size();
  int[] colors = new int[n];
  Arrays.fill(colors, -1);
  for (int i = 0; i < n; i++) {
    if (colors[i] == -1) {
      if (!dfsCheck(graph, i, colors, 0)) return false;
    }
  }
  return true;
}

boolean dfsCheck(List<List<Integer>> graph, int node, int[] colors, int color) {
  colors[node] = color;
  for (int neighbor : graph.get(node)) {
    if (colors[neighbor] == -1) {
      if (!dfsCheck(graph, neighbor, colors, 1 - color)) return false;
    } else if (colors[neighbor] == color) {
      return false;
    }
  }
  return true;
}

medium

A. Missing check for null graph

B. Colors array not initialized properly

C. Incorrect color flip in recursive call

D. DFS color assignment logic is correct, no bug

Solution

1. Step 1: Review color initialization

   Colors array is initialized with -1, meaning uncolored, which is correct.

2. Step 2: Check DFS color assignment and recursion

   DFS assigns current node color, then recursively assigns opposite color (1 - color) to neighbors. If neighbor has same color, returns false.

3. Step 3: Confirm logic correctness

   The logic correctly detects bipartite property using DFS and color flipping. No bug found.

4. Final Answer:

   DFS color assignment logic is correct, no bug -> Option D

5. Quick Check:

   DFS color flip and checks are correct [OK]

Hint: DFS flips color 0 and 1 to check bipartite [OK]

Common Mistakes:

• Forgetting to flip color in recursion
• Not initializing colors array
• Returning true too early

5. Given a graph with vertices 0 to 5 and edges: 0-1, 1-2, 2-3, 3-4, 4-5, 5-0, and 1-4, is the graph bipartite? Explain why.

hard

A. Yes, because all vertices can be colored the same

B. No, because it contains an odd length cycle

C. Yes, because it contains only even length cycles

D. No, because it has isolated vertices

Solution

1. Step 1: Identify cycles in the graph

   The graph edges form a 6-node cycle: 0-1-2-3-4-5-0 and an extra edge 1-4.

2. Step 2: Check for odd length cycles

   There exists an odd length cycle: 1-4-5-0-1 (length 4 is even, but 1-4-5-0-1 is actually length 4, so check carefully). Actually, the cycle 1-4-5-0-1 is length 4 (even). But consider cycle 1-2-3-4-1: edges 1-2,2-3,3-4,4-1 is length 4 (even). However, the presence of edge 1-4 creates a triangle cycle 1-4-5-0-1? No, 1-4-5-0-1 is length 4. But check for odd cycles: 1-4-5-0-1 is length 4, 0-1-4 is length 3? No edge 0-4. But edge 1-4 exists, 4-5, 5-0, 0-1. So cycle 1-4-5-0-1 is length 4. No odd cycles. But check cycle 1-4-5-0-1 is length 4. So no odd cycles. So graph is bipartite.

3. Step 3: Determine bipartite property

   Absence of odd length cycles means the graph is bipartite.

4. Final Answer:

   Yes, because it contains only even length cycles -> Option C

5. Quick Check:

   No odd cycles = bipartite [OK]

Hint: Odd cycles break bipartite property [OK]

Common Mistakes:

• Falsely assuming extra edge creates odd cycle (e.g., nonexistent 1-5)
• Miscalculating cycle lengths
• Confusing isolated vertices with bipartite condition