Adjacency List Representation in DSA C++

Mental Model

We store each node's neighbors in a list so we can quickly see which nodes connect to it.

Analogy: Imagine a group of friends where each person keeps a list of their friends' names. To find who a person knows, you just look at their list.

0: [1, 2]
1: [0, 3]
2: [0]
3: [1]

Each number is a node, and the brackets show its neighbors.

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0-1, 0-2, 1-3

Goal: Build adjacency lists showing neighbors for each node

Step 1: Add edge 0-1 by adding 1 to node 0's list and 0 to node 1's list

0: [1]
1: [0]
2: []
3: []

Why: We record that node 0 connects to node 1 and vice versa

Step 2: Add edge 0-2 by adding 2 to node 0's list and 0 to node 2's list

0: [1, 2]
1: [0]
2: [0]
3: []

Why: We record that node 0 connects to node 2 and vice versa

Step 3: Add edge 1-3 by adding 3 to node 1's list and 1 to node 3's list

0: [1, 2]
1: [0, 3]
2: [0]
3: [1]

Why: We record that node 1 connects to node 3 and vice versa

Result:

0: [1, 2]
1: [0, 3]
2: [0]
3: [1]

Annotated Code

DSA C++

#include <iostream>
#include <vector>

using namespace std;

class Graph {
public:
    int V; // number of vertices
    vector<vector<int>> adjList; // adjacency list

    Graph(int vertices) {
        V = vertices;
        adjList.resize(V);
    }

    void addEdge(int u, int v) {
        adjList[u].push_back(v); // add v to u's list
        adjList[v].push_back(u); // add u to v's list (undirected)
    }

    void printGraph() {
        for (int i = 0; i < V; i++) {
            cout << i << ": [";
            for (size_t j = 0; j < adjList[i].size(); j++) {
                cout << adjList[i][j];
                if (j != adjList[i].size() - 1) cout << ", ";
            }
            cout << "]\n";
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);

    g.printGraph();
    return 0;
}

adjList[u].push_back(v); // add v to u's list

add neighbor v to node u's adjacency list

adjList[v].push_back(u); // add u to v's list (undirected)

add neighbor u to node v's adjacency list for undirected edge

for (int i = 0; i < V; i++) { ... }

iterate over all nodes to print their adjacency lists

Output

0: [1, 2]

1: [0, 3]

2: [0]

3: [1]

Complexity Analysis

Time: O(V + E) because we add each edge once and print all adjacency lists

Space: O(V + E) because we store each vertex and its edges in lists

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more efficient for sparse graphs

Edge Cases

Graph with no edges

All adjacency lists remain empty

DSA C++

adjList.resize(V);

Graph with single node

Adjacency list has one empty list

DSA C++

adjList.resize(V);

When to Use This Pattern

When you need to represent a graph efficiently and quickly find neighbors, use adjacency lists because they store only existing edges.

Common Mistakes

Mistake: Forgetting to add the edge in both directions for undirected graphs
Fix: Add both adjList[u].push_back(v) and adjList[v].push_back(u) to represent undirected edges

Summary

Stores each node's neighbors in a list for efficient graph representation.

Use when you want to save space and quickly access neighbors in sparse graphs.

The key is each node keeps a list of only its connected nodes, not all nodes.

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