Adjacency List Representation in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list is a way to represent a graph where each node stores a list of its neighboring nodes. It shows which nodes are directly connected to each node.

intermediate

How does an adjacency list differ from an adjacency matrix?

An adjacency list uses less space for sparse graphs by storing only neighbors for each node, while an adjacency matrix uses a 2D array showing connections between all pairs of nodes, which can waste space.

beginner

In Rust, which data structure is commonly used to implement an adjacency list?

A vector of vectors (Vec) is commonly used, where each index represents a node and stores a list of its neighbors.

intermediate

What is the time complexity to find all neighbors of a node using an adjacency list?

It is O(k), where k is the number of neighbors of that node, because the adjacency list stores only the neighbors directly.

beginner

Why is adjacency list preferred for sparse graphs?

Because it only stores existing edges, saving memory compared to adjacency matrix which stores all possible edges, even if many are missing.

What does each element in an adjacency list represent?

A A node and its neighbors

B A node and its weight

C A pair of disconnected nodes

D A matrix row

Each element in an adjacency list represents a node and the list of nodes it connects to directly.

Which Rust data structure is best for adjacency list?

A String

B HashMap<String, String>

C Vec<i32>

D Vec<Vec<usize>>

Vec> is used to store neighbors for each node by index.

What is the space complexity of adjacency list for a graph with V vertices and E edges?

A O(V)

B O(V^2)

C O(V + E)

D O(E^2)

Adjacency list stores all vertices and edges, so space is proportional to V + E.

Which graph type benefits most from adjacency list?

A Sparse graph

B Complete graph

C Dense graph

D Disconnected graph

Sparse graphs have fewer edges, so adjacency list saves space.

How do you find neighbors of a node in adjacency list?

A Check all nodes for edges

B Look up the node's list in the adjacency list

C Scan the entire matrix row

D Use a stack

Neighbors are stored directly in the node's list in adjacency list.

Explain how an adjacency list represents a graph and why it is efficient for sparse graphs.

Think about how connections are stored only where they exist.

Describe how you would implement an adjacency list in Rust and how to access neighbors of a node.

Consider vectors of vectors and indexing by node number.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list of all nodes without connections

B. A matrix showing distances between nodes

C. A list where each node stores its connected neighbors

D. A queue of nodes to visit next

Solution

1. Step 1: Understand graph representation

   An adjacency list stores each node with a list of its neighbors, showing direct connections.

2. Step 2: Compare options

   Only A list where each node stores its connected neighbors describes this correctly; others describe different structures or concepts.

3. Final Answer:

   A list where each node stores its connected neighbors -> Option C

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list = node with its neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking adjacency list stores distances
• Mixing up with traversal queues

2. Which Rust data structure is best suited to represent an adjacency list for a graph with nodes labeled 0 to n-1?

easy

A. Vec

B. HashMap

C. Vec<usize>

D. HashSet<usize>

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for nodes 0 to n-1 is a vector where each index holds a vector of neighbors.

2. Step 2: Match Rust types

   Vec matches this: outer Vec for nodes, inner Vec for neighbors. Others don't store neighbors per node properly.

3. Final Answer:

   Vec -> Option A

4. Quick Check:

   Vec of Vecs = adjacency list [OK]

Hint: Use Vec for adjacency list in Rust [OK]

Common Mistakes:

• Using HashMap with single usize value instead of list
• Using Vec<usize> which holds only one neighbor list
• Using HashSet which doesn't map nodes to neighbors

3. Given the following Rust code, what is the printed adjacency list?

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

medium

A. [[0], [1], [2]]

B. [[1], [2], [0]]

C. [[], [], []]

D. [[2], [0], [1]]

Solution

1. Step 1: Trace graph initialization

   graph starts as three empty vectors: [[], [], []]

2. Step 2: Apply push operations

   graph[0].push(1) -> [[1], [], []] graph[1].push(2) -> [[1], [2], []] graph[2].push(0) -> [[1], [2], [0]]

3. Final Answer:

   [[1], [2], [0]] -> Option B

4. Quick Check:

   Push neighbors correctly = [[1], [2], [0]] [OK]

Hint: Follow push calls step-by-step [OK]

Common Mistakes:

• Mixing indices when pushing neighbors
• Assuming graph is empty after pushes
• Confusing order of neighbors

4. Identify the error in this Rust code snippet for creating an adjacency list:

let mut graph: Vec = Vec::new();
graph[0].push(1);

medium

A. Vec::new() cannot be mutable

B. usize type is incorrect for adjacency list

C. push method does not exist for Vec

D. graph is empty, so graph[0] access causes panic

Solution

1. Step 1: Analyze graph initialization

   graph is empty Vec with no elements, so graph[0] does not exist.

2. Step 2: Understand indexing error

   Accessing graph[0] causes runtime panic because index 0 is out of bounds.

3. Final Answer:

   graph is empty, so graph[0] access causes panic -> Option D

4. Quick Check:

   Empty Vec indexing = panic [OK]

Hint: Initialize Vec with size before indexing [OK]

Common Mistakes:

• Assuming Vec::new() has elements
• Confusing mutability with initialization
• Thinking push is invalid method

5. You want to represent a directed graph with 4 nodes using an adjacency list in Rust. Which code correctly initializes the graph and adds edges from node 0 to 1 and 2, and from node 2 to 3?

hard

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

B. let mut graph = Vec::new();
graph[0].push(1);
graph[0].push(2);
graph[2].push(3);

C. let mut graph = vec![0; 4];
graph[0] = 1;
graph[0] = 2;
graph[2] = 3;

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

Solution

1. Step 1: Check graph initialization

   let mut graph = vec![vec![], vec![], vec![], vec![]]; graph[0].push(1); graph[0].push(2); graph[2].push(3); initializes a Vec of Vecs with 4 empty vectors, ready to hold neighbors.

2. Step 2: Verify edge additions

   graph[0].push(1) and graph[0].push(2) add edges from node 0 to 1 and 2; graph[2].push(3) adds edge from 2 to 3.

3. Step 3: Identify errors in other options

   let mut graph = Vec::new(); graph[0].push(1); graph[0].push(2); graph[2].push(3);: graph is empty Vec, indexing causes panic. let mut graph = vec![0; 4]; graph[0] = 1; graph[0] = 2; graph[2] = 3;: graph is Vec<usize>, not Vec; push invalid. let mut graph = vec![vec![0]; 4]; graph[0].push(1); graph[0].push(2); graph[2].push(3);: graph initialized with vec![vec![0]; 4] means each node starts with neighbor 0, incorrect.

4. Final Answer:

   let mut graph = vec![vec![], vec![], vec![], vec![]]; graph[0].push(1); graph[0].push(2); graph[2].push(3); -> Option A

5. Quick Check:

   Vec of empty Vecs + push edges = correct [OK]

Hint: Initialize Vec with empty Vecs before pushing [OK]

Common Mistakes:

• Using empty Vec without size causes panic
• Initializing with repeated vec![0] adds wrong neighbors
• Using Vec<usize> instead of Vec