Bipartite Graph Check in DSA Java - Execution Trace

Concept Flow - Bipartite Graph Check

Start with uncolored graph

↓

Pick an unvisited node

↓

Assign color 0 to start node

↓

Use BFS/DFS to visit neighbors

↓

For each neighbor

↓

If uncolored

↓

Assign opposite color

↓

Continue BFS/DFS

↓

All nodes colored without conflict?

Yes↓

Graph is Bipartite

No↓

Graph is Not Bipartite

Start from an unvisited node, color it, then use BFS/DFS to color neighbors with opposite colors. If a conflict arises, graph is not bipartite.

Execution Sample

DSA Java

boolean isBipartite(int[][] graph) {
  int[] colors = new int[graph.length];
  Arrays.fill(colors, -1);
  for (int i = 0; i < graph.length; i++) {
    if (colors[i] == -1 && !bfsCheck(graph, colors, i)) return false;
  }
  return true;
}

Checks if the graph is bipartite by coloring nodes using BFS and verifying no conflicts.

Execution Table

Step	Operation	Current Node	Neighbor	Colors Array	Queue State	Visual State
1	Initialize colors	-	-	[-1, -1, -1, -1, -1, -1]	[]	All nodes uncolored
2	Start BFS from node 0	0	-	[0, -1, -1, -1, -1, -1]	[0]	Node 0 colored 0
3	Visit neighbors of 0	0	1	[0, 1, -1, -1, -1, -1]	[1]	Node 1 colored 1 (opposite of 0)
4	Visit neighbors of 0	0	3	[0, 1, -1, 1, -1, -1]	[1, 3]	Node 3 colored 1 (opposite of 0)
5	Dequeue node 1	1	-	[0, 1, -1, 1, -1, -1]	[3]	Processing node 1
6	Visit neighbors of 1	1	0	[0, 1, -1, 1, -1, -1]	[3]	Neighbor 0 already colored 0, no conflict
7	Visit neighbors of 1	1	2	[0, 1, 0, 1, -1, -1]	[3, 2]	Node 2 colored 0 (opposite of 1)
8	Dequeue node 3	3	-	[0, 1, 0, 1, -1, -1]	[2]	Processing node 3
9	Visit neighbors of 3	3	0	[0, 1, 0, 1, -1, -1]	[2]	Neighbor 0 already colored 0, no conflict
10	Visit neighbors of 3	3	4	[0, 1, 0, 1, 0, -1]	[2, 4]	Node 4 colored 0 (opposite of 3)
11	Dequeue node 2	2	-	[0, 1, 0, 1, 0, -1]	[4]	Processing node 2
12	Visit neighbors of 2	2	1	[0, 1, 0, 1, 0, -1]	[4]	Neighbor 1 already colored 1, no conflict
13	Visit neighbors of 2	2	5	[0, 1, 0, 1, 0, 1]	[4, 5]	Node 5 colored 1 (opposite of 2)
14	Dequeue node 4	4	-	[0, 1, 0, 1, 0, 1]	[5]	Processing node 4
15	Visit neighbors of 4	4	3	[0, 1, 0, 1, 0, 1]	[5]	Neighbor 3 already colored 1, no conflict
16	Dequeue node 5	5	-	[0, 1, 0, 1, 0, 1]	[]	Processing node 5
17	Visit neighbors of 5	5	2	[0, 1, 0, 1, 0, 1]	[]	Neighbor 2 already colored 0, no conflict
18	All nodes processed	-	-	[0, 1, 0, 1, 0, 1]	[]	Graph is bipartite
19	Check next unvisited node	-	-	N/A	N/A	No unvisited nodes left, end

💡 All nodes colored without conflict, BFS completed, graph is bipartite

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 10	After Step 13	Final
colors	[-1, -1, -1, -1, -1, -1]	[0, -1, -1, -1, -1, -1]	[0, 1, -1, 1, -1, -1]	[0, 1, 0, 1, -1, -1]	[0, 1, 0, 1, 0, -1]	[0, 1, 0, 1, 0, 1]	[0, 1, 0, 1, 0, 1]
queue	[]	[0]	[1, 3]	[3, 2]	[2, 4]	[4, 5]	[]
current_node	N/A	0	0	1	3	2	5

Key Moments - 3 Insights

Why do we assign colors as 0 and 1 instead of other numbers?

Colors 0 and 1 represent two groups. Using two distinct values helps easily check if neighbors have opposite colors (see execution_table steps 3, 4, 7).

What happens if a neighbor already has the same color as the current node?

This means the graph is not bipartite because two connected nodes share the same group. The BFS would return false immediately (not shown in this example, but see concept_flow).

Why do we start BFS from every unvisited node?

Because the graph can be disconnected. We must check each component separately (see execution_table step 19).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what color is assigned to node 2?

A 0

B 1

C -1

D 2

💡 Hint

Check the Colors Array column at step 7 in execution_table

At which step does the queue become empty, indicating BFS completion?

A Step 16

B Step 18

C Step 19

D Step 14

💡 Hint

Look at the Queue State column in execution_table rows to find when it becomes []

If node 3 was colored 0 instead of 1 at step 4, what would happen?

A Graph would still be bipartite

B Conflict detected later, graph not bipartite

C No change in colors array

D Queue would be empty immediately

💡 Hint

Refer to concept_flow and key_moments about color conflicts

Concept Snapshot

Bipartite Graph Check:
- Use BFS/DFS to color nodes with 2 colors (0 and 1)
- Start from unvisited nodes to cover disconnected graphs
- If a neighbor has same color, graph is not bipartite
- Colors array tracks node colors (-1 means uncolored)
- Return true if no conflicts found after full traversal

Full Transcript

To check if a graph is bipartite, we start with all nodes uncolored (-1). We pick an unvisited node and color it 0. Using BFS, we visit neighbors and color them with the opposite color (1). If a neighbor is already colored with the same color as the current node, the graph is not bipartite. We repeat this for all disconnected parts of the graph. If no conflicts arise, the graph is bipartite. The colors array and queue track progress. This method ensures all nodes are checked and colored properly.

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