Adjacency List Representation in DSA Rust - Execution Trace

Concept Flow - Adjacency List Representation

Start: Create empty adjacency list

↓

Add vertex to graph

↓

Add edge: from vertex A to vertex B

↓

Update adjacency list: append B to A's list

↓

Repeat for all edges

↓

Graph represented as adjacency list

↓

Use adjacency list for traversal or queries

Build an adjacency list by adding vertices and edges, storing neighbors in lists for each vertex.

Execution Sample

DSA Rust

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

This code creates a graph with 4 vertices, each having a list of connected vertices.

Execution Table

Step	Operation	Nodes in Graph	Pointer Changes	Visual State
1	Initialize empty graph	0	None	{}
2	Add vertex 0	1	graph.push(vec![])	{0: []}
3	Add vertex 1	2	graph.push(vec![])	{0: [], 1: []}
4	Add vertex 2	3	graph.push(vec![])	{0: [], 1: [], 2: []}
5	Add vertex 3	4	graph.push(vec![])	{0: [], 1: [], 2: [], 3: []}
6	Add edge 0 -> 1	4	graph[0].push(1)	{0: [1], 1: [], 2: [], 3: []}
7	Add edge 0 -> 2	4	graph[0].push(2)	{0: [1, 2], 1: [], 2: [], 3: []}
8	Add edge 1 -> 0	4	graph[1].push(0)	{0: [1, 2], 1: [0], 2: [], 3: []}
9	Add edge 1 -> 3	4	graph[1].push(3)	{0: [1, 2], 1: [0, 3], 2: [], 3: []}
10	Add edge 2 -> 0	4	graph[2].push(0)	{0: [1, 2], 1: [0, 3], 2: [0], 3: []}
11	Add edge 3 -> 1	4	graph[3].push(1)	{0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
12	Final adjacency list ready	4	None	{0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}

💡 All vertices and edges added, adjacency list fully built.

Variable Tracker

Variable	Start	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	Final
graph	{}	{0: []}	{0: [], 1: []}	{0: [], 1: [], 2: []}	{0: [], 1: [], 2: [], 3: []}	{0: [1], 1: [], 2: [], 3: []}	{0: [1, 2], 1: [], 2: [], 3: []}	{0: [1, 2], 1: [0], 2: [], 3: []}	{0: [1, 2], 1: [0, 3], 2: [], 3: []}	{0: [1, 2], 1: [0, 3], 2: [0], 3: []}	{0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}	{0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}

Key Moments - 3 Insights

Why do we store neighbors in a list for each vertex?

Because the adjacency list keeps track of which vertices are connected to each vertex, storing neighbors in a list makes it easy to find all connected nodes quickly, as shown in steps 6-11.

Why do we add edges in both directions for an undirected graph?

Because in an undirected graph, connections go both ways, so we add each edge twice (e.g., 0->1 and 1->0) to represent this, as seen in steps 6 and 8.

What does the empty list mean when we add a new vertex?

An empty list means the vertex has no edges yet. This is shown in steps 2-5 where vertices are added with empty neighbor lists.

Visual Quiz - 3 Questions

Look at the execution table, what is the adjacency list of vertex 1 after step 9?

A [0]

B [1, 2]

C [0, 3]

D []

💡 Hint

Check the 'Visual State' column at step 9 for vertex 1's neighbors.

At which step does vertex 3 get its first neighbor added?

A Step 5

B Step 11

C Step 9

D Step 7

💡 Hint

Look for when graph[3] changes from empty to having elements in the 'Visual State' column.

If we skip adding edge 1 -> 0, how would the adjacency list for vertex 1 change after step 9?

A [3]

B [0, 3]

C []

D [1, 2]

💡 Hint

Compare the adjacency list for vertex 1 in step 9 with and without adding edge 1 -> 0.

Concept Snapshot

Adjacency List Representation:
- Use a list (or vector) for each vertex to store neighbors.
- Add vertices with empty lists first.
- Add edges by appending neighbors to these lists.
- For undirected graphs, add edges in both directions.
- Efficient for sparse graphs and quick neighbor lookup.

Full Transcript

Adjacency List Representation builds a graph by creating a list for each vertex to hold its neighbors. We start with an empty graph, add vertices with empty neighbor lists, then add edges by appending connected vertices to these lists. For undirected graphs, edges are added in both directions to represent two-way connections. This structure is efficient for storing and traversing graphs, especially when they have fewer edges compared to the number of vertices.

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