Adjacency List Representation in DSA C++ - 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 saves space by only storing edges that exist.

beginner

How does adjacency list differ from adjacency matrix?

Adjacency list stores neighbors only, using less space for sparse graphs. Adjacency matrix uses a 2D array to store all possible edges, using more space.

intermediate

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

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

beginner

Show a simple C++ code snippet to declare an adjacency list for a graph with 5 nodes.

std::vector adjList(5); // 5 nodes, each with an empty list of neighbors

beginner

Why is adjacency list preferred for sparse graphs?

Because it only stores existing edges, saving memory and making traversal faster compared to adjacency matrix which stores all possible edges.

What data structure is commonly used to implement adjacency lists?

A Stack

B 2D array

C Array of lists or vectors

D Queue

Adjacency lists are usually implemented as an array (or vector) where each element is a list or vector of neighbors.

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

A O(V^2)

B O(V + E)

C O(E^2)

D O(V)

Adjacency list stores all vertices and edges, so space is proportional to number of vertices plus edges.

Which graph type benefits most from adjacency list representation?

A No edges graph

B Dense graph

C Complete graph

D Sparse graph

Sparse graphs have fewer edges, so adjacency list saves space by storing only existing edges.

How do you add an edge from node 1 to node 3 in an adjacency list?

A adjList[1].push_back(3);

B adjList[3].push_back(1);

C adjList[1][3] = 1;

D adjList[3][1] = 1;

To add an edge from node 1 to 3, append 3 to the neighbors list of node 1.

What is the time complexity to check if an edge exists between two nodes in adjacency list?

A O(k) where k is neighbors count

B O(V)

C O(1)

D O(E)

You must search the neighbors list of one node, which takes time proportional to its number of neighbors.

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

Think about how edges are stored only if they exist.

Describe how to add and traverse edges using adjacency list in C++.

Focus on code structure and simple loops.

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