Adjacency List Representation in DSA C++ - Execution Trace

Concept Flow - Adjacency List Representation

Start

↓

Create empty adjacency list

↓

For each edge (u, v)

↓

Add v to u's list

↓

Add u to v's list (if undirected)

↓

Repeat for all edges

↓

Adjacency list ready

Build an adjacency list by adding each edge's nodes to each other's lists for undirected graphs.

Execution Sample

DSA C++

int V = 3;
vector<int> adj[V];
adj[0].push_back(1);
adj[1].push_back(0);
adj[1].push_back(2);
adj[2].push_back(1);

Create adjacency list for graph with edges 0-1 and 1-2.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize empty adjacency list for 3 vertices	0: [] 1: [] 2: []	None	0: [] 1: [] 2: []
2	Add edge 0-1: add 1 to 0's list	0: [1] 1: [] 2: []	adj[0] points to [1]	0: [1] 1: [] 2: []
3	Add edge 0-1: add 0 to 1's list	0: [1] 1: [0] 2: []	adj[1] points to [0]	0: [1] 1: [0] 2: []
4	Add edge 1-2: add 2 to 1's list	0: [1] 1: [0, 2] 2: []	adj[1] points to [0, 2]	0: [1] 1: [0, 2] 2: []
5	Add edge 1-2: add 1 to 2's list	0: [1] 1: [0, 2] 2: [1]	adj[2] points to [1]	0: [1] 1: [0, 2] 2: [1]
6	All edges added	0: [1] 1: [0, 2] 2: [1]	No change	0: [1] 1: [0, 2] 2: [1]

💡 All edges processed, adjacency list fully built.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
adj[0]	[]	[1]	[1]	[1]	[1]	[1]
adj[1]	[]	[]	[0]	[0, 2]	[0, 2]	[0, 2]
adj[2]	[]	[]	[]	[]	[1]	[1]

Key Moments - 3 Insights

Why do we add each node to the other's list in an undirected graph?

Because edges go both ways, so adj[0] has 1 and adj[1] has 0 (see steps 2 and 3 in execution_table).

What does the adjacency list look like before adding any edges?

All lists are empty arrays as shown in step 1 of execution_table.

Why do we use vectors (or lists) for each vertex?

To store all connected nodes dynamically, shown by how adj[1] grows from [] to [0, 2] in steps 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the content of adj[1]?

A [1]

B [0, 2]

C [2]

D []

💡 Hint

Check the 'Nodes in List' column at step 4 in execution_table.

At which step does adj[2] first get a node added?

A Step 5

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Pointer Changes' and 'Visual State' columns for adj[2] in execution_table.

If the graph was directed and edge 1->2 only, which step would be removed?

A Step 3

B Step 2

C Step 5

D Step 4

💡 Hint

Directed graphs add edge only one way; check which step adds 1 to 2's list.

Concept Snapshot

Adjacency List Representation:
- Use array/vector of lists for vertices
- Each list stores connected nodes
- For undirected graphs, add edges both ways
- Efficient for sparse graphs
- Access neighbors by indexing vertex list

Full Transcript

Adjacency List Representation stores graph edges by keeping a list of neighbors for each vertex. We start with empty lists for all vertices. For each edge, we add the connected vertex to each other's list if the graph is undirected. This builds a structure where each vertex points to its neighbors. The example shows a graph with vertices 0, 1, 2 and edges 0-1 and 1-2. The adjacency list updates step-by-step, adding neighbors to each vertex's list. This method is memory efficient for graphs with fewer edges and allows quick access to neighbors.

Practice

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

easy

A. A list storing only isolated vertices

B. A matrix showing connections between all pairs of vertices

C. A list of all edges without vertex information

D. A list where each vertex stores a list of its adjacent vertices

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each vertex and the vertices it connects to directly.

2. Step 2: Compare with other graph representations

   Unlike adjacency matrix, adjacency list focuses on neighbors per vertex, not all pairs.

3. Final Answer:

   A list where each vertex stores a list of its adjacent vertices -> Option D

4. Quick Check:

   Adjacency list = vertex with neighbors [OK]

Hint: Adjacency list = vertex + its neighbors list [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores all edges as pairs only
• Assuming it stores isolated vertices only

2. Which of the following is the correct C++ syntax to declare an adjacency list for a graph with n vertices using vectors?

easy

A. vector<int> adj[n];

B. vector adj(n);

C. vector adj[n];

D. vector<int> adj(n);

Solution

1. Step 1: Understand vector of vectors declaration

   To represent adjacency list, we use vector adj(n); to create n empty lists.

2. Step 2: Check other options for correctness

   vector<int> adj[n]; declares a non-standard variable-length array (VLA) of vectors. vector adj[n]; is invalid syntax. vector<int> adj(n); declares a single vector of ints, not a list of lists.

3. Final Answer:

   vector adj(n); -> Option B

4. Quick Check:

   Use vector of vectors for adjacency list [OK]

Hint: Use vector for adjacency list [OK]

Common Mistakes:

• Using vector<int> adj(n) which is 1D vector
• Incorrect syntax like vector adj[n];
• Confusing array of vectors with vector of vectors

3. What will be the output adjacency list after executing the following C++ code?

int V = 3;
vector adj(V);
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(2);
for(int i = 0; i < V; i++) {
  cout << i << ": ";
  for(auto v : adj[i]) cout << v << " ";
  cout << endl;
}

medium

A. 0: 1 2
1: 2
2:

B. 0: 2 1
1: 2
2:

C. 0: 1
1: 2
2: 0 1

D. 0:
1: 0 2
2: 1

Solution

1. Step 1: Trace adjacency list insertions

   adj[0] gets 1 and 2 pushed, adj[1] gets 2 pushed, adj[2] remains empty.

2. Step 2: Print adjacency list content

   For i=0: prints "0: 1 2 ", for i=1: "1: 2 ", for i=2: "2: " (empty).

3. Final Answer:

   0: 1 2 1: 2 2: -> Option A

4. Quick Check:

   Push_back order preserved in adjacency list [OK]

Hint: Push_back order shows neighbors in insertion order [OK]

Common Mistakes:

• Assuming adjacency list is sorted automatically
• Mixing up indices and values
• Printing empty lists incorrectly

4. Identify the error in the following code snippet that tries to add an edge to an adjacency list for an undirected graph:

int V = 4;
vector adj(V);
int u = 1, v = 3;
adj[u].push_back(v);
// Missing line here

medium

A. The code should also add adj[v].push_back(u) for undirected edge

B. The vector declaration is incorrect

C. The indices u and v are out of range

D. push_back should be replaced with insert

Solution

1. Step 1: Understand undirected graph edge addition

   For undirected graphs, edges must be added both ways: u to v and v to u.

2. Step 2: Check code for missing reverse edge

   Code adds edge from u to v but misses adj[v].push_back(u), so graph is incomplete.

3. Final Answer:

   The code should also add adj[v].push_back(u) for undirected edge -> Option A

4. Quick Check:

   Undirected edge = add both directions [OK]

Hint: Add edges both ways for undirected graphs [OK]

Common Mistakes:

• Adding edge only one way in undirected graph
• Using wrong vector syntax
• Confusing push_back with insert

5. Given a directed graph with 4 vertices and edges: (0->1), (0->2), (1->2), (2->0), (2->3), (3->3), which adjacency list representation correctly shows the graph?

hard

A. 0: 2 1
1: 2
2: 3 0
3: 3

B. 0: 1 2
1: 0 2
2: 0 3
3: 3

C. 0: 1 2
1: 2
2: 0 3
3: 3

D. 0: 1 2
1: 2
2: 3
3: 0 3

Solution

1. Step 1: List edges for each vertex

   Vertex 0 connects to 1 and 2, vertex 1 connects to 2, vertex 2 connects to 0 and 3, vertex 3 connects to itself (3).

2. Step 2: Match edges to adjacency list options

   0: 1 2 1: 2 2: 0 3 3: 3 matches exactly the edges given. Others have wrong order or extra edges.

3. Final Answer:

   0: 1 2 1: 2 2: 0 3 3: 3 -> Option C

4. Quick Check:

   Match edges to adjacency list exactly [OK]

Hint: Write edges per vertex to verify adjacency list [OK]

Common Mistakes:

• Mixing order of neighbors
• Adding edges not in original graph
• Missing self-loop at vertex 3