Why Graphs Exist and What Trees Cannot Model in DSA Rust - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a graph node with an adjacency list.

DSA Rust

struct Node {
    value: i32,
    neighbors: Vec<[1]>,
}

Drag options to blanks, or click blank then click option'

Abool

Bi32

CString

DNode

Attempts:

3 left

💡 Hint

Common Mistakes

Using primitive types like i32 instead of Node for neighbors.

The neighbors field holds a list of adjacent nodes, so its type is Vec.

2fill in blank

medium

Complete the code to add an edge between two nodes in an undirected graph.

DSA Rust

fn add_edge(node1: &mut Node, node2: &mut Node) {
    node1.neighbors.push([1]);
    node2.neighbors.push(node1.clone());
}

Drag options to blanks, or click blank then click option'

Anode1.value

Bnode2.clone()

Cnode2.value

Dnode1.clone()

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing node1 to node1's neighbors instead of node2.

To add an edge, node1's neighbors should include node2, so push node2.clone().

3fill in blank

hard

Fix the error in the code to check if a graph contains a cycle.

DSA Rust

fn has_cycle(node: &Node, visited: &mut Vec<bool>, parent: usize) -> bool {
    visited[node.value as usize] = true;
    for neighbor in &node.neighbors {
        if !visited[neighbor.value as usize] {
            if has_cycle(neighbor, visited, node.value as usize) [1] {
                return true;
            }
        } else if neighbor.value as usize != parent {
            return true;
        }
    }
    false
}

Drag options to blanks, or click blank then click option'

A== false

B== true

C!= false

D!= true

Attempts:

3 left

💡 Hint

Common Mistakes

Using '== false' which reverses the logic.

The recursive call returns a bool; checking if it is not false means a cycle was found.

4fill in blank

hard

Fill both blanks to create a graph adjacency list using a HashMap.

DSA Rust

use std::collections::HashMap;

let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
graph.entry([1]).or_insert(Vec::new()).push([2]);

Drag options to blanks, or click blank then click option'

A1

B2

C3

D4

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the order of nodes in the edge.

We add an edge from node 1 to node 2 in the adjacency list.

5fill in blank

hard

Fill all three blanks to implement a BFS traversal starting from a node.

DSA Rust

use std::collections::VecDeque;

fn bfs(start: i32, graph: &HashMap<i32, Vec<i32>>) {
    let mut visited = std::collections::HashSet::new();
    let mut queue = VecDeque::new();
    queue.push_back([1]);
    visited.insert([2]);

    while let Some(node) = queue.pop_front() {
        println!("Visited: {}", node);
        if let Some(neighbors) = graph.get(&node) {
            for &neighbor in neighbors {
                if !visited.contains(&neighbor) {
                    queue.push_back(neighbor);
                    visited.insert([3]);
                }
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Astart

Bnode

Cneighbor

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Inserting wrong nodes into visited set causing infinite loops.

Start BFS by pushing and marking the start node visited. Insert neighbors when discovered.

Practice

1. Why do we need graphs when we already have trees in data structures?

easy

A. Because graphs can represent connections between nodes that trees cannot, like cycles and multiple parents.

B. Because trees are faster to traverse than graphs.

C. Because trees use less memory than graphs.

D. Because graphs only store numbers, while trees store strings.

Solution

1. Step 1: Understand tree structure limitations

   Trees have a strict hierarchy where each node has only one parent and no cycles.

2. Step 2: Identify graph capabilities

   Graphs allow nodes to have multiple connections, including cycles and multiple parents, which trees cannot model.

3. Final Answer:

   Because graphs can represent connections between nodes that trees cannot, like cycles and multiple parents. -> Option A

4. Quick Check:

   Graphs model cycles and multiple parents [OK]

Hint: Graphs allow cycles and multiple parents; trees do not [OK]

Common Mistakes:

• Thinking trees can have cycles
• Confusing memory use with structure capability
• Assuming graphs only store numbers

2. Which of the following Rust code snippets correctly declares an undirected graph using adjacency lists?

easy

A. let graph: Vec<usize> = vec![0, 1, 2];

B. let graph: Vec = vec![vec![], vec![], vec![]];

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

D. let graph: Vec<(usize, usize)> = vec![(0, 1), (1, 2)];

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list is a vector of vectors where each inner vector holds neighbors of a node.

2. Step 2: Match code to adjacency list

   let graph: Vec = vec![vec![], vec![], vec![]]; declares a vector of vectors of usize, suitable for adjacency lists.

3. Final Answer:

   let graph: Vec = vec![vec![], vec![], vec![]]; -> Option B

4. Quick Check:

   Adjacency list = Vec [OK]

Hint: Adjacency list uses Vec of Vec for neighbors [OK]

Common Mistakes:

• Using Vec<usize> instead of Vec
• Using HashMap with wrong types
• Using edge list instead of adjacency list

3. Consider this Rust code that builds a graph and prints neighbors of node 1:

let mut graph = vec![vec![], vec![], vec![]];
graph[0].push(1);
graph[1].push(0);
graph[1].push(2);
graph[2].push(1);
println!("{:?}", graph[1]);

What is the output?

medium

A. [2]

B. [1, 2]

C. [0, 1]

D. [0, 2]

Solution

1. Step 1: Trace graph construction

   graph[1] has neighbors pushed: 0 and 2, so graph[1] = [0, 2].

2. Step 2: Print neighbors of node 1

   Printing graph[1] outputs [0, 2].

3. Final Answer:

   [0, 2] -> Option D

4. Quick Check:

   Neighbors of node 1 = [0, 2] [OK]

Hint: Check which neighbors were pushed to node 1's list [OK]

Common Mistakes:

• Confusing node indices
• Assuming neighbors include the node itself
• Mixing order of neighbors

4. This Rust code tries to add an edge to a graph but causes a runtime error:

let mut graph = vec![vec![], vec![]];
graph[0].push(1);
graph[1].push(0);
graph[2].push(1);

What is the error and how to fix it?

medium

A. Index out of bounds error; fix by increasing graph size to include index 2.

B. Type mismatch error; fix by changing Vec to HashMap.

C. Syntax error; fix by adding semicolons.

D. Logic error; fix by removing graph[1].push(0).

Solution

1. Step 1: Identify cause of runtime error

   graph has length 2, so graph[2] access is out of bounds causing panic.

2. Step 2: Fix by resizing graph

   Increase graph size to at least 3 elements to allow graph[2].push(1).

3. Final Answer:

   Index out of bounds error; fix by increasing graph size to include index 2. -> Option A

4. Quick Check:

   Accessing graph[2] with size 2 causes error [OK]

Hint: Check vector size before indexing [OK]

Common Mistakes:

• Ignoring vector size limits
• Confusing syntax and runtime errors
• Removing unrelated lines

5. You want to model a social network where users can be friends with multiple people and friendships can be mutual or one-way. Why is a graph a better choice than a tree for this model?

hard

A. Because trees can only store numbers, not user data.

B. Because trees are faster to search in social networks.

C. Because graphs allow cycles and multiple connections, representing mutual and one-way friendships.

D. Because graphs use less memory than trees.

Solution

1. Step 1: Understand social network connections

   Users can have multiple friends, and friendships can be mutual (cycles) or one-way (directed edges).

2. Step 2: Compare tree and graph capabilities

   Trees cannot represent cycles or multiple parents, but graphs can model these complex relationships.

3. Step 3: Conclude best data structure

   Graphs are better because they allow cycles and multiple connections needed for social networks.

4. Final Answer:

   Because graphs allow cycles and multiple connections, representing mutual and one-way friendships. -> Option C

5. Quick Check:

   Social network needs cycles and multiple edges [OK]

Hint: Social networks need cycles and multiple edges; use graphs [OK]

Common Mistakes:

• Thinking trees can model mutual friendships
• Confusing data type storage with structure capability
• Assuming trees use less memory always