Adjacency List Representation in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare an adjacency list for a graph with 5 vertices.

DSA C++

std::vector<int> adj[[1]];

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

A5

B4

C6

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using a size less than the number of vertices causes out-of-bound errors.

Using zero size means no adjacency list is created.

The adjacency list is declared as an array of vectors with size equal to the number of vertices, which is 5 here.

2fill in blank

medium

Complete the code to add an edge from vertex 2 to vertex 3 in the adjacency list.

DSA C++

adj[2].[1](3);

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

Ainsert

Bpush_back

Cadd

Dappend

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert without an iterator causes errors.

Using append or add are not valid vector methods in C++.

The push_back method adds an element to the end of the vector, which is how edges are added in adjacency lists.

3fill in blank

hard

Fix the error in the code to correctly print all neighbors of vertex 1.

DSA C++

for (int i = 0; i < adj[1].[1](); i++) {
    std::cout << adj[1][i] << " ";
}

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

Alength

Bcapacity

Csize

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using length() causes compilation errors.

Using capacity() returns allocated space, not actual elements.

The size() method returns the number of elements in the vector, which is needed to loop through neighbors.

4fill in blank

hard

Fill both blanks to add an undirected edge between vertices 0 and 4.

DSA C++

adj[[1]].push_back([2]);
adj[[2]].push_back([1]);

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

A0

B4

C1

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Adding edge only one way creates a directed edge.

Mixing vertex numbers causes wrong connections.

For an undirected edge, add vertex 4 to vertex 0's list and vertex 0 to vertex 4's list.

5fill in blank

hard

Fill all three blanks to create an adjacency list for a graph with 3 vertices and edges (0-1), (1-2).

DSA C++

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

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

A3

B1

C2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong vertex numbers for edges.

Setting wrong array size causes errors.

The graph has 3 vertices. Edge (0-1) adds 1 to adj[0]. Edge (1-2) adds 2 to adj[1].

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