Bipartite Graph Check in DSA Rust - Execution Trace

Concept Flow - Bipartite Graph Check

Start with uncolored graph

↓

Pick an uncolored node

↓

Assign color 0

↓

Use BFS/DFS to visit neighbors

↓

If neighbor uncolored, assign opposite color

↓

If neighbor colored same as current, stop: Not Bipartite

↓

Repeat for all nodes

↓

If no conflicts, graph is Bipartite

We color nodes using two colors while traversing. If a conflict arises, graph is not bipartite.

Execution Sample

DSA Rust

fn is_bipartite(graph: &Vec<Vec<usize>>) -> bool {
    let mut colors = vec![-1; graph.len()];
    for i in 0..graph.len() {
        if colors[i] == -1 {
            if !bfs_check(i, graph, &mut colors) {
                return false;
            }
        }
    }
    true
}

Checks if graph is bipartite by coloring nodes with BFS.

Execution Table

Step	Operation	Current Node	Neighbor	Colors Array	Conflict Detected	Visual State
1	Start BFS from node 0	0	-	[-1, -1, -1, -1]	No	[0(-1)] - [1(-1), 3(-1)]
2	Color node 0 with 0	0	-	[0, -1, -1, -1]	No	[0(0)] - [1(-1), 3(-1)]
3	Visit neighbor 1	0	1	[0, -1, -1, -1]	No	[0(0)] - [1(-1), 3(-1)]
4	Color neighbor 1 with 1	1	-	[0, 1, -1, -1]	No	[0(0)] - [1(1)] - [2(-1), 3(-1)]
5	Visit neighbor 3	0	3	[0, 1, -1, -1]	No	[0(0)] - [1(1)] - [3(-1)]
6	Color neighbor 3 with 1	3	-	[0, 1, -1, 1]	No	[0(0)] - [1(1)] - [3(1)]
7	Visit neighbors of 1	1	0	[0, 1, -1, 1]	No	[0(0)] - [1(1)] - [3(1)]
8	Neighbor 0 already colored 0 (opposite), continue	1	0	[0, 1, -1, 1]	No	[0(0)] - [1(1)] - [3(1)]
9	Visit neighbor 2	1	2	[0, 1, -1, 1]	No	[0(0)] - [1(1)] - [2(-1)] - [3(1)]
10	Color neighbor 2 with 0	2	-	[0, 1, 0, 1]	No	[0(0)] - [1(1)] - [2(0)] - [3(1)]
11	Visit neighbors of 3	3	0	[0, 1, 0, 1]	No	[0(0)] - [1(1)] - [2(0)] - [3(1)]
12	Neighbor 0 already colored 0 (opposite), continue	3	0	[0, 1, 0, 1]	No	[0(0)] - [1(1)] - [2(0)] - [3(1)]
13	Visit neighbors of 2	2	1	[0, 1, 0, 1]	No	[0(0)] - [1(1)] - [2(0)] - [3(1)]
14	Neighbor 1 already colored 1 (opposite), continue	2	1	[0, 1, 0, 1]	No	[0(0)] - [1(1)] - [2(0)] - [3(1)]
15	All nodes visited, no conflicts	-	-	[0, 1, 0, 1]	No	[0(0)] - [1(1)] - [2(0)] - [3(1)]

💡 All nodes colored without conflict, graph is bipartite.

Variable Tracker

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

Key Moments - 3 Insights

Why do we assign colors only when a node is uncolored?

Because if a node is already colored, it means it was visited before. Assigning color again could cause conflicts. See steps 7-8 where neighbor 0 is already colored 0, so we just check for conflict.

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

This means the graph is not bipartite. The algorithm stops immediately. In the execution table, no such conflict occurs, but if it did, 'Conflict Detected' would be 'Yes' and the function would return false.

Why do we need to check all nodes, not just start from node 0?

Because the graph might be disconnected. We must check each uncolored node to cover all components. The loop in the code ensures this by checking colors[i] == -1 for all i.

Visual Quiz - 3 Questions

Look at the execution table, what is the color of node 3 after step 6?

A 0

B 1

C -1

D 2

💡 Hint

Check the 'Colors Array' column at step 6 in the execution table.

At which step does the algorithm color node 2?

A Step 10

B Step 4

C Step 9

D Step 15

💡 Hint

Look for the step where 'Color neighbor 2 with 0' happens in the 'Operation' column.

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

A No conflict, graph still bipartite

B Conflict detected at neighbor 2

C Conflict detected at neighbor 0

D Algorithm would run infinitely

💡 Hint

Refer to the 'Conflict Detected' logic and colors of neighbors in the execution table.

Concept Snapshot

Bipartite Graph Check:
- Color nodes with 2 colors (0 and 1)
- Use BFS/DFS to assign colors to neighbors
- If neighbor has same color, graph is not bipartite
- Check all nodes for disconnected graphs
- Return true if no conflicts found

Full Transcript

This visualization shows how to check if a graph is bipartite by coloring nodes with two colors using BFS. We start from an uncolored node, assign color 0, then visit neighbors assigning opposite colors. If a neighbor already has the same color, the graph is not bipartite. The execution table traces each step, showing node colors and checks. The variable tracker shows how colors and current node change. Key moments clarify common confusions like why we only color uncolored nodes and why all nodes must be checked. The quiz tests understanding of colors at steps and conflict detection. The snapshot summarizes the process simply.

Practice

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

easy

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

B. It has an equal number of vertices and edges

C. It contains at least one cycle of odd length

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 sets so that no edge connects vertices within the same set.

2. Step 2: Check options against definition

   Its vertices can be divided into two groups with no edges inside the same group matches this definition exactly. Options A, B, and D describe unrelated properties.

3. Final Answer:

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

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

2. Which Rust code snippet correctly declares an adjacency list for an undirected graph to check bipartiteness?

easy

A. let graph: Vec<(usize, usize)> = Vec::new();

B. let graph: Vec<usize> = vec![0; n];

C. let graph: HashMap = HashMap::new();

D. let graph: Vec = vec![vec![]; n];

Solution

1. Step 1: Identify adjacency list type

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

2. Step 2: Match code snippet to adjacency list

   let graph: Vec = vec![vec![]; n]; declares a vector of vectors of usize, initialized with empty vectors for each vertex, which is correct. Options A, B, and C do not represent adjacency lists properly.

3. Final Answer:

   let graph: Vec = vec![vec![]; n]; -> Option D

4. Quick Check:

   Adjacency list = Vec of Vecs [OK]

Hint: Adjacency list is Vec in Rust [OK]

Common Mistakes:

• Using Vec<usize> instead of Vec
• Using HashMap with wrong types
• Using tuple vector which is edge list, not adjacency list

3. Given the following Rust code snippet to check bipartiteness, what is the output?

let graph = vec![
    vec![1, 3],
    vec![0, 2],
    vec![1, 3],
    vec![0, 2],
];

fn is_bipartite(graph: &Vec) -> bool {
    let n = graph.len();
    let mut colors = vec![-1; n];
    for i in 0..n {
        if colors[i] == -1 {
            let mut stack = vec![i];
            colors[i] = 0;
            while let Some(u) = stack.pop() {
                for &v in &graph[u] {
                    if colors[v] == -1 {
                        colors[v] = 1 - colors[u];
                        stack.push(v);
                    } else if colors[v] == colors[u] {
                        return false;
                    }
                }
            }
        }
    }
    true
}

println!("{}", is_bipartite(&graph));

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Analyze graph structure

   The graph has 4 vertices with edges forming a square (0-1-2-3-0). This is an even cycle, which is bipartite.

2. Step 2: Trace DFS coloring

   The code colors vertex 0 as 0, then neighbors 1 and 3 as 1, then neighbors 2 as 0. No conflicts occur, so it returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Even cycle graph is bipartite = true [OK]

Hint: Even cycles are bipartite, so output is true [OK]

Common Mistakes:

• Thinking all cycles are non-bipartite
• Confusing stack usage with queue
• Missing color conflict check

4. The following Rust code attempts to check if a graph is bipartite but has a bug. What is the bug?

fn is_bipartite(graph: &Vec) -> bool {
    let n = graph.len();
    let mut colors = vec![-1; n];
    for i in 0..n {
        if colors[i] == -1 {
            let mut stack = vec![i];
            colors[i] = 0;
            while let Some(u) = stack.pop() {
                for &v in &graph[u] {
                    if colors[v] == -1 {
                        colors[v] = colors[u]; // Bug here
                        stack.push(v);
                    } else if colors[v] == colors[u] {
                        return false;
                    }
                }
            }
        }
    }
    true
}

medium

A. Stack is used instead of queue, causing infinite loop

B. Colors assigned to neighbors are same as current vertex, causing wrong bipartite check

C. colors vector is initialized with zeros instead of -1

D. Graph parameter should be mutable

Solution

1. Step 1: Identify color assignment bug

   The code assigns neighbors the same color as current vertex, which breaks bipartite property requiring opposite colors.

2. Step 2: Understand impact on bipartite check

   This causes false negatives or positives because neighbors must have opposite colors, so the check fails.

3. Final Answer:

   Colors assigned to neighbors are same as current vertex, causing wrong bipartite check -> Option B

4. Quick Check:

   Neighbors must have opposite colors [OK]

Hint: Neighbors must get opposite color, not same [OK]

Common Mistakes:

• Assigning same color to neighbors
• Confusing stack and queue usage
• Initializing colors incorrectly

5. You have a graph with vertices 0 to 5 and edges: (0-1), (1-2), (2-3), (3-0), (3-4), (4-5). Which of the following statements is true about its bipartiteness?

hard

A. The graph is not bipartite because it contains an odd cycle (3-4-5)

B. The graph is not bipartite because it contains an even cycle (0-1-2-3)

C. The graph is bipartite because it contains no odd cycles

D. The graph is bipartite because all vertices have degree 2 or less

Solution

1. Step 1: Identify cycles in the graph

   The graph has a cycle 0-1-2-3-0 which is length 4 (even). The path 3-4-5 is a chain, not a cycle.

2. Step 2: Check bipartite condition

   Graphs with no odd cycles are bipartite. Since the only cycle is even, the graph is bipartite.

3. Final Answer:

   The graph is bipartite because it contains no odd cycles -> Option C

4. Quick Check:

   No odd cycles means bipartite [OK]

Hint: Check for odd cycles; none means bipartite [OK]

Common Mistakes:

• Mistaking chains for cycles
• Thinking even cycles break bipartiteness
• Assuming degree affects bipartiteness