Bipartite Graph Check in DSA C++ - Execution Trace

Concept Flow - Bipartite Graph Check

Start with graph

↓

Pick uncolored node

↓

Assign color 0

↓

Use BFS/DFS to visit neighbors

↓

For each neighbor

↓

If uncolored

↓

Assign opposite

↓

Continue BFS

↓

Repeat for all nodes

↓

If no conflicts -> Bipartite

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

Execution Sample

DSA C++

bool isBipartite(vector<vector<int>>& graph) {
  int n = graph.size();
  vector<int> color(n, -1);
  for (int i = 0; i < n; i++) {
    if (color[i] == -1) {
      if (!bfsColor(i, graph, color)) return false;
    }
  }
  return true;
}

This code checks if the graph is bipartite by coloring nodes using BFS.

Execution Table

Step	Operation	Current Node	Neighbor	Color Changes	Conflict Detected	Graph Color State	Visual State
1	Start BFS from node 0	0	-	color[0] = 0	No	[0:0, 1:-1, 2:-1, 3:-1]	0(Blue) -> ? -> ? -> ?
2	Visit neighbors of 0	0	1	color[1] = 1	No	[0:0, 1:1, 2:-1, 3:-1]	0(Blue) -> 1(Red) -> ? -> ?
3	Visit neighbors of 0	0	3	color[3] = 1	No	[0:0, 1:1, 2:-1, 3:1]	0(Blue) -> 1(Red) -> ? -> 3(Red)
4	Visit neighbors of 1	1	0	No change	No	[0:0, 1:1, 2:-1, 3:1]	0(Blue) -> 1(Red) -> ? -> 3(Red)
5	Visit neighbors of 1	1	2	color[2] = 0	No	[0:0, 1:1, 2:0, 3:1]	0(Blue) -> 1(Red) -> 2(Blue) -> 3(Red)
6	Visit neighbors of 3	3	0	No change	No	[0:0, 1:1, 2:0, 3:1]	0(Blue) -> 1(Red) -> 2(Blue) -> 3(Red)
7	Visit neighbors of 3	3	2	No change	No	[0:0, 1:1, 2:0, 3:1]	0(Blue) -> 1(Red) -> 2(Blue) -> 3(Red)
8	Visit neighbors of 2	2	1	No change	No	[0:0, 1:1, 2:0, 3:1]	0(Blue) -> 1(Red) -> 2(Blue) -> 3(Red)
9	Visit neighbors of 2	2	3	No change	No	[0:0, 1:1, 2:0, 3:1]	0(Blue) -> 1(Red) -> 2(Blue) -> 3(Red)
10	All nodes colored, no conflict	-	-	-	No	[0:0, 1:1, 2:0, 3:1]	0(Blue) -> 1(Red) -> 2(Blue) -> 3(Red)

💡 All nodes visited and colored without conflict, graph is bipartite.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 10
color	[-1, -1, -1, -1]	[0, -1, -1, -1]	[0, 1, -1, -1]	[0, 1, -1, 1]	[0, 1, 0, 1]	[0, 1, 0, 1]
queue	[]	[0]	[1, 3]	[3]	[3, 2]	[]

Key Moments - 3 Insights

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

Colors 0 and 1 represent two groups. Using two distinct values helps check if neighbors have opposite colors. See execution_table steps 1-3 where color 0 and 1 are assigned.

What happens if a neighbor already has the same color?

If a neighbor has the same color, it means the graph is not bipartite. The algorithm detects this conflict and stops. In the table, 'Conflict Detected' would be 'Yes' if this happens.

Why do we start BFS from uncolored nodes only?

Starting from uncolored nodes ensures all disconnected parts of the graph are checked. See execution_sample code line with 'if (color[i] == -1)'.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what color is assigned to node 1?

A 0

B -1 (uncolored)

C 1

D 2

💡 Hint

Check the 'Color Changes' and 'Graph Color State' columns at Step 2.

At which step does the algorithm color node 2?

A Step 5

B Step 7

C Step 3

D Step 9

💡 Hint

Look at the 'Color Changes' column for when color[2] is assigned.

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

A No conflict, graph still bipartite

B Conflict detected later, graph not bipartite

C Algorithm would skip node 3

D Node 3 would be recolored automatically

💡 Hint

Refer to the 'Conflict Detected' column and how same colors on neighbors cause failure.

Concept Snapshot

Bipartite Graph Check:
- Use BFS or DFS to color nodes with 2 colors (0 and 1).
- Start from uncolored nodes, assign color 0.
- Assign opposite color to neighbors.
- If neighbor has same color, graph is not bipartite.
- If all nodes colored without conflict, graph is bipartite.

Full Transcript

To check if a graph is bipartite, we assign colors to nodes using BFS or DFS. We start from an uncolored node and assign color 0. Then, we visit its neighbors and assign the opposite color 1. We continue this process for all nodes. If at any point a neighbor has the same color as the current node, the graph is not bipartite. Otherwise, if all nodes are colored without conflict, the graph is bipartite. The execution table shows step-by-step how nodes are colored and how conflicts are checked.

Practice

1. What does it mean if a graph is bipartite?

easy

A. It contains at least one cycle of odd length

B. It has an equal number of vertices and edges

C. Its vertices can be divided into two groups with no edges inside the same group

D. All vertices have the same degree

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph means vertices can be split into two sets where no edge connects vertices within the same 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 C

4. Quick Check:

   Bipartite = 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 graphs must have cycles
• Assuming all vertices have same degree

2. Which of the following C++ code snippets correctly initializes a graph as an adjacency list for bipartite check?

easy

A. vector graph(n);

B. vector<int> graph(n);

C. int graph[n][n];

D. map graph;

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for a graph with n vertices is best represented as vector of vectors: vector graph(n);

2. Step 2: Check other options

   vector<int> graph(n); is a vector of ints, not suitable for adjacency lists. int graph[n][n]; is a 2D array but less flexible. map graph; is a map of int to int, not adjacency list.

3. Final Answer:

   vector graph(n); -> Option A

4. Quick Check:

   Adjacency list = vector of vectors [OK]

Hint: Use vector of vectors for adjacency list in C++ [OK]

Common Mistakes:

• Using vector<int> instead of vector
• Using fixed size arrays limiting flexibility
• Using map which is not adjacency list

3. What is the output of the following code snippet that checks if a graph is bipartite?

int n = 4;
vector graph = {{1,3}, {0,2}, {1,3}, {0,2}};
vector<int> color(n, -1);

function dfs = [&](int node, int c) {
    color[node] = c;
    for (int neigh : graph[node]) {
        if (color[neigh] == -1) {
            if (!dfs(neigh, 1 - c)) return false;
        } else if (color[neigh] == c) {
            return false;
        }
    }
    return true;
};

bool result = true;
for (int i = 0; i < n; i++) {
    if (color[i] == -1) {
        if (!dfs(i, 0)) {
            result = false;
            break;
        }
    }
}
cout << (result ? "YES" : "NO") << endl;

medium

A. Runtime Error

B. NO

C. Compilation Error

D. YES

Solution

1. Step 1: Analyze graph structure

   The graph edges connect vertices 0-1, 0-3, 1-2, 2-3 forming a square (even cycle), which is bipartite.

2. Step 2: Trace DFS coloring

   DFS colors nodes alternatingly. No adjacent nodes share the same color, so dfs returns true for all nodes.

3. Final Answer:

   YES -> Option D

4. Quick Check:

   Even cycle graph is bipartite = YES [OK]

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

Common Mistakes:

• Assuming all cycles are non-bipartite
• Confusing color assignment logic
• Ignoring disconnected components

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

bool dfs(int node, int c, vector& graph, vector<int>& color) {
    color[node] = c;
    for (int neigh : graph[node]) {
        if (color[neigh] == -1) {
            dfs(neigh, 1 - c, graph, color);
        } else if (color[neigh] == c) {
            return false;
        }
    }
    return true;
}

medium

A. Missing return value check for recursive dfs call

B. Wrong color assignment to nodes

C. Using vector<int> instead of vector<bool>

D. Incorrect graph representation

Solution

1. Step 1: Check recursive call handling

   The recursive dfs call result is not checked. If it returns false, the function should also return false immediately.

2. Step 2: Explain fix

   Adding 'if (!dfs(...)) return false;' ensures early exit on conflict detection.

3. Final Answer:

   Missing return value check for recursive dfs call -> Option A

4. Quick Check:

   Always check recursive call results in DFS [OK]

Hint: Return false immediately if recursive DFS fails [OK]

Common Mistakes:

• Ignoring recursive call return values
• Assigning wrong colors
• Using wrong data structures for graph

5. Given a graph with 5 vertices and edges: (0-1), (1-2), (2-3), (3-4), (4-1), which statement is true about its bipartite property?

hard

A. The graph is bipartite because it has no odd cycles

B. The graph is not bipartite because it contains an odd cycle

C. The graph is bipartite because all vertices have degree 2

D. The graph is not bipartite because it is disconnected

Solution

1. Step 1: Identify cycles in the graph

   The edges form a cycle: 1-2-3-4-1 which has 4 edges (even length). However, the full cycle including vertices 0-1-4-3-2-1 forms a cycle of length 5 (odd cycle): 0-1-4-3-2-1 (0-1,1-4,4-3,3-2,2-1).

2. Step 2: Check bipartite condition

   Since the graph contains an odd cycle of length 5, it is not bipartite.

3. Step 3: Re-examine options

   The graph is bipartite because it has no odd cycles is false. The graph is not bipartite because it contains an odd cycle is true. The graph is bipartite because all vertices have degree 2 is incorrect reasoning. The graph is not bipartite because it is disconnected is false because the graph is connected.

4. Final Answer:

   The graph is not bipartite because it contains an odd cycle -> Option B

5. Quick Check:

   Odd cycle means not bipartite [OK]

Hint: Check cycle lengths: odd cycle means not bipartite [OK]

Common Mistakes:

• Miscounting cycle length
• Confusing connectivity with bipartite property
• Assuming degree affects bipartite