Bipartite Graph Check in DSA C# - Execution Trace

Concept Flow - Bipartite Graph Check

Start with graph

↓

Pick uncolored node

↓

Assign color 1

↓

Use BFS/DFS to visit neighbors

↓

If neighbor uncolored -> assign opposite color

↓

If neighbor colored same as current -> Not Bipartite

↓

Repeat for all nodes

↓

If no conflicts -> Graph is Bipartite

We start with an uncolored graph, pick nodes to color alternately using BFS or DFS, and check for conflicts to decide if the graph is bipartite.

Execution Sample

DSA C#

bool IsBipartite(int[][] graph) {
  int n = graph.Length;
  int[] colors = new int[n];
  for (int i = 0; i < n; i++) {
    if (colors[i] == 0 && !BFS(i, graph, colors)) return false;
  }
  return true;
}

This code checks if the graph is bipartite by coloring nodes using BFS and verifying no two adjacent nodes share the same color.

Execution Table

Step	Operation	Current Node	Neighbor Node	Colors Array	Conflict Detected	Visual State
1	Start BFS from node 0	0	-	[0,0,0,0]	No	0(white) 1(?) 2(?) 3(?)
2	Color node 0 with color 1	0	-	[1,0,0,0]	No	0(blue) 1(?) 2(?) 3(?)
3	Visit neighbors of 0: node 1	0	1	[1,0,0,0]	No	0(blue) 1(?) 2(?) 3(?)
4	Color neighbor 1 with color -1	1	-	[1,-1,0,0]	No	0(blue) 1(red) 2(?) 3(?)
5	Visit neighbors of 1: node 0	1	0	[1,-1,0,0]	No	0(blue) 1(red) 2(?) 3(?)
6	Neighbor 0 already colored with opposite color, continue	1	0	[1,-1,0,0]	No	0(blue) 1(red) 2(?) 3(?)
7	Visit neighbors of 1: node 2	1	2	[1,-1,0,0]	No	0(blue) 1(red) 2(?) 3(?)
8	Color neighbor 2 with color 1	2	-	[1,-1,1,0]	No	0(blue) 1(red) 2(blue) 3(?)
9	Visit neighbors of 2: node 1	2	1	[1,-1,1,0]	No	0(blue) 1(red) 2(blue) 3(?)
10	Neighbor 1 already colored with opposite color, continue	2	1	[1,-1,1,0]	No	0(blue) 1(red) 2(blue) 3(?)
11	Visit neighbors of 2: node 3	2	3	[1,-1,1,0]	No	0(blue) 1(red) 2(blue) 3(?)
12	Color neighbor 3 with color -1	3	-	[1,-1,1,-1]	No	0(blue) 1(red) 2(blue) 3(red)
13	Visit neighbors of 3: node 2	3	2	[1,-1,1,-1]	No	0(blue) 1(red) 2(blue) 3(red)
14	Neighbor 2 already colored with opposite color, continue	3	2	[1,-1,1,-1]	No	0(blue) 1(red) 2(blue) 3(red)
15	All nodes visited, no conflicts found	-	-	[1,-1,1,-1]	No	Graph is Bipartite
16	End	-	-	[1,-1,1,-1]	No	Bipartite check complete

💡 All nodes colored without conflict, so graph is bipartite.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	After Step 12	Final
colors	[0,0,0,0]	[1,0,0,0]	[1,-1,0,0]	[1,-1,1,0]	[1,-1,1,-1]	[1,-1,1,-1]
current_node	-	0	1	2	3	-
conflict_detected	No	No	No	No	No	No

Key Moments - 3 Insights

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

Using 0 means uncolored, so we use 1 and -1 to represent two different colors clearly. See execution_table rows 2, 4, 8, and 12 where colors are assigned.

What happens if a neighbor is already colored with the same color?

That means the graph is not bipartite. The BFS would detect a conflict. In this example, no conflict occurs as shown in execution_table rows 6, 10, and 14.

Why do we start BFS from every uncolored node?

Because the graph can be disconnected. We must check each component. See execution_table row 1 where BFS starts from node 0, and the loop in the code sample.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what color is assigned to node 1?

A 1

B -1

C 0

D Not colored yet

💡 Hint

Check the Colors Array column at step 4 in execution_table.

At which step does the algorithm color node 3?

A Step 8

B Step 12

C Step 4

D Step 15

💡 Hint

Look for the step where neighbor 3 is colored in execution_table.

If a neighbor node is found colored with the same color during BFS, what happens?

A Continue BFS normally

B Assign a new color to the neighbor

C Return false, graph is not bipartite

D Restart BFS from that neighbor

💡 Hint

Refer to the concept_flow and key_moments about conflict detection.

Concept Snapshot

Bipartite Graph Check:
- Use BFS or DFS to color nodes with two colors (1 and -1).
- Start from uncolored nodes to cover disconnected graphs.
- If a neighbor has the same color, graph is not bipartite.
- If no conflicts, graph is bipartite.
- Colors array tracks node colors: 0=uncolored, 1 and -1 are two colors.

Full Transcript

To check if a graph is bipartite, we color nodes using two colors while traversing the graph with BFS or DFS. We start from each uncolored node to cover all parts of the graph. When visiting neighbors, if a neighbor is uncolored, we assign the opposite color. If a neighbor is already colored with the same color, the graph is not bipartite. If we finish without conflicts, the graph is bipartite. The colors array keeps track of node colors, where 0 means uncolored, and 1 and -1 represent the two colors. This process ensures no two adjacent nodes share the same color, which is the definition of a bipartite graph.

Practice

1. What does it mean for a graph to be 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 is one where vertices can be split into two sets with edges only between sets, not inside a set.

2. Step 2: Compare options with definition

   Its vertices can be divided into two groups with no edges inside the same group matches this definition exactly, while others 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 = two groups, 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 C# data structure is best to represent a graph for bipartite check?

easy

A. List adjacency list

B. Dictionary adjacency list

C. int[,] adjacency matrix

D. HashSet<int> for vertices only

Solution

1. Step 1: Identify graph representation needs

   We need to store edges efficiently and access neighbors quickly for bipartite check.

2. Step 2: Evaluate options

   Dictionary allows flexible vertex keys and fast neighbor lookup, better than fixed-size arrays or sets.

3. Final Answer:

   Dictionary adjacency list -> Option B

4. Quick Check:

   Dictionary adjacency list = best for flexible graphs [OK]

Hint: Use Dictionary for flexible graph edges [OK]

Common Mistakes:

• Using HashSet only stores vertices, no edges
• Adjacency matrix wastes space for sparse graphs
• List lacks vertex key mapping

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

var graph = new Dictionary {
  {0, new List<int>{1,3}},
  {1, new List<int>{0,2}},
  {2, new List<int>{1,3}},
  {3, new List<int>{2,0}}
};
bool IsBipartite(Dictionary g) {
  var color = new Dictionary();
  foreach(var node in g.Keys) {
    if(!color.ContainsKey(node)) {
      var queue = new Queue<int>();
      queue.Enqueue(node);
      color[node] = 0;
      while(queue.Count > 0) {
        var u = queue.Dequeue();
        foreach(var v in g[u]) {
          if(!color.ContainsKey(v)) {
            color[v] = 1 - color[u];
            queue.Enqueue(v);
          } else if(color[v] == color[u]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}
Console.WriteLine(IsBipartite(graph));

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze the graph structure

   The graph forms a cycle of length 4: 0-1-2-3-0.

2. Step 2: Check bipartite condition on even cycle

   Even cycles are bipartite, but here the cycle is length 4 (even), so it should be bipartite. However, the code returns false if adjacent nodes have same color.

3. Step 3: Trace coloring

   Coloring alternates 0 and 1 around the cycle, no conflict occurs, so function returns true.

4. Final Answer:

   True -> Option A

5. Quick Check:

   Even cycle graph is bipartite = True [OK]

Hint: Even cycles are bipartite; odd cycles are not [OK]

Common Mistakes:

• Assuming all cycles are not bipartite
• Confusing color assignment logic
• Ignoring queue BFS traversal

4. Identify the bug in this bipartite check code snippet:

bool CheckBipartite(Dictionary graph) {
  var color = new Dictionary();
  foreach(var node in graph.Keys) {
    if(!color.ContainsKey(node)) {
      color[node] = 0;
      var stack = new Stack<int>();
      stack.Push(node);
      while(stack.Count > 0) {
        var u = stack.Pop();
        foreach(var v in graph[u]) {
          if(!color.ContainsKey(v)) {
            color[v] = color[u];
            stack.Push(v);
          } else if(color[v] == color[u]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

medium

A. Colors assigned to neighbors are same as current node, should be opposite

B. Stack should be replaced with queue for BFS

C. Missing initialization of color dictionary

D. No return statement for true case

Solution

1. Step 1: Review color assignment logic

   Neighbors must have opposite colors to current node for bipartite check.

2. Step 2: Identify incorrect assignment

   Code assigns neighbor color same as current node, causing false negatives.

3. Final Answer:

   Colors assigned to neighbors are same as current node, should be opposite -> Option A

4. Quick Check:

   Neighbor colors must differ [OK]

Hint: Neighbors must have opposite colors, not same [OK]

Common Mistakes:

• Assigning same color to neighbors
• Confusing stack vs queue (both work but BFS preferred)
• Forgetting to initialize colors

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 cycles are even length

B. No, because it has a self-loop

C. No, because it contains an odd cycle including edges 1-2-3-4-1

D. Yes, because it has no cycles

Solution

1. Step 1: Identify cycles in the graph

   The graph has a large cycle 0-1-2-3-4-5-0 (length 6, even), and with edge 1-4, cycles 1-2-3-4-1 (length 4, even) and 0-1-4-5-0 (length 4, even).

2. Step 2: Check for odd-length cycles

   No odd-length cycles exist. A graph is bipartite if and only if it has no odd-length cycles.

3. Final Answer:

   No, because it contains an odd cycle including edges 1-2-3-4-1 -> Option C

4. Quick Check:

   Odd cycle means not bipartite [OK]

Hint: Check for odd cycles to decide bipartite [OK]

Common Mistakes:

• Miscounting cycle lengths
• Assuming any cycle means not bipartite
• Ignoring extra edges creating odd cycles