Bipartite Graph Check in DSA Rust

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 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 the graph can be colored using two colors so that no connected nodes share the same color.

Step 1: Start coloring node 1 with color A

1[A] -> 2[ ] -> 3[ ] -> 4[ ]

Why: We pick a starting node and assign it a color to begin the check.

Step 2: Color node 2 with color B because it connects to node 1

1[A] -> 2[B] -> 3[ ] -> 4[ ]

Why: Neighbors must have opposite colors to keep bipartite property.

Step 3: Color node 3 with color A because it connects to node 2

1[A] -> 2[B] -> 3[A] -> 4[ ]

Why: Continue alternating colors along edges.

Step 4: Color node 4 with color B because it connects to node 3

1[A] -> 2[B] -> 3[A] -> 4[B]

Why: Maintain alternating colors for neighbors.

Step 5: Check edge 4-1: node 4 is B, node 1 is A, no conflict

1[A] -> 2[B] -> 3[A] -> 4[B]

Why: All edges connect nodes of different colors, so graph is bipartite.

Result:

1[A] -> 2[B] -> 3[A] -> 4[B]
Graph is bipartite: true

Annotated Code

DSA Rust

use std::collections::VecDeque;

fn is_bipartite(graph: &Vec<Vec<usize>>) -> bool {
    let n = graph.len();
    let mut colors = vec![None; n];

    for start in 0..n {
        if colors[start].is_some() {
            continue; // already colored
        }

        colors[start] = Some(true); // assign first color
        let mut queue = VecDeque::new();
        queue.push_back(start);

        while let Some(node) = queue.pop_front() {
            let current_color = colors[node].unwrap();
            for &neighbor in &graph[node] {
                if colors[neighbor].is_none() {
                    colors[neighbor] = Some(!current_color); // assign opposite color
                    queue.push_back(neighbor);
                } else if colors[neighbor] == Some(current_color) {
                    return false; // same color neighbor found, not bipartite
                }
            }
        }
    }
    true
}

fn main() {
    // Graph: 1-2, 2-3, 3-4, 4-1 (0-based: 0-1,1-2,2-3,3-0)
    let graph = vec![
        vec![1, 3], // node 0
        vec![0, 2], // node 1
        vec![1, 3], // node 2
        vec![2, 0], // node 3
    ];

    let result = is_bipartite(&graph);
    println!("Graph is bipartite: {}", result);
}

colors[start] = Some(true); // assign first color

assign starting node color to begin bipartite check

while let Some(node) = queue.pop_front() {

process nodes in BFS order to color neighbors

colors[neighbor] = Some(!current_color); // assign opposite color

color neighbor with opposite color to current node

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

detect conflict if neighbor has same color, graph not bipartite

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 storing colors and BFS queue

vs Alternative: Compared to checking all color combinations (exponential), BFS coloring is efficient and linear.

Edge Cases

Empty graph (no nodes)

Returns true since no edges violate bipartite property

DSA Rust

for start in 0..n { if colors[start].is_some() { continue; }

Graph with one node and no edges

Returns true as single node can be colored any color

DSA Rust

colors[start] = Some(true); // assign first color

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

Returns false because coloring conflicts occur

DSA Rust

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

When to Use This Pattern

When you need to check if a graph can be split into two groups with no internal edges, use bipartite check with BFS coloring to detect conflicts.

Common Mistakes

Mistake: Not checking all connected components in disconnected graphs
Fix: Loop over all nodes and start BFS only if node is uncolored

Mistake: Assigning same color to neighbors without checking
Fix: Always assign opposite color to neighbors and check for conflicts

Summary

Checks if a graph can be divided into two groups with edges only between groups.

Use when you want to know if a graph is bipartite or can be 2-colored without conflicts.

The key insight is to color nodes in BFS order assigning opposite colors to neighbors and detect conflicts.

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