Adjacency List Representation in DSA C++ - Build from Scratch

Adjacency List Representation

📖 Scenario: You are working on a simple social network where each person can have friends. You want to represent the friendships using a graph. Each person is a node, and each friendship is an edge connecting two nodes.

🎯 Goal: Build an adjacency list representation of the graph using C++ STL vectors. You will create the graph, add friendships, and then print the adjacency list to see who is friends with whom.

📋 What You'll Learn

Create an adjacency list using a vector of vectors of integers

Add edges (friendships) between nodes

Print the adjacency list showing each node and its connected nodes

💡 Why This Matters

🌍 Real World

Graphs are used to represent networks like social connections, maps, and computer networks. Adjacency lists efficiently store these connections.

💼 Career

Understanding adjacency lists is essential for software engineers working with graph algorithms, network analysis, and data structures.

1

Create the adjacency list data structure

Create a variable called adjList which is a std::vector<std::vector<int>> with size 5 to represent 5 nodes.

DSA C++

#include 
#include 

int main() {
    // Create adjacency list with 5 nodes
    // Your code here
    return 0;
}

Hint

Use std::vector<std::vector<int>> adjList(5); to create a vector of 5 empty vectors.

2

Add edges (friendships) to the adjacency list

Add edges to adjList to represent these friendships: node 0 is friends with 1 and 4, node 1 is friends with 0 and 2, node 2 is friends with 1 and 3, node 3 is friends with 2 and 4, node 4 is friends with 0 and 3. Use adjList[node].push_back(friend) to add each friendship.

DSA C++

#include 
#include 

int main() {
    std::vector> adjList(5);
    // Add edges to adjList
    // Your code here
    return 0;
}

Hint

Use adjList[node].push_back(friend) for each friendship pair.

3

Print the adjacency list

Use a for loop with variable i from 0 to 4 to iterate over adjList. Inside it, use another for loop with variable friendNode to iterate over adjList[i]. Print the node i followed by all its friends separated by spaces on the same line.

DSA C++

#include 
#include 

int main() {
    std::vector> adjList(5);
    adjList[0].push_back(1);
    adjList[0].push_back(4);
    adjList[1].push_back(0);
    adjList[1].push_back(2);
    adjList[2].push_back(1);
    adjList[2].push_back(3);
    adjList[3].push_back(2);
    adjList[3].push_back(4);
    adjList[4].push_back(0);
    adjList[4].push_back(3);

    // Print adjacency list
    // Your code here
    return 0;
}

Hint

Use nested loops to print each node and its friends on one line.

4

Display the final adjacency list output

Write a print statement that outputs the adjacency list in the format: each line starts with the node number, a colon, and then all connected nodes separated by spaces. The output should exactly match the example.

DSA C++

#include 
#include 

int main() {
    std::vector> adjList(5);
    adjList[0].push_back(1);
    adjList[0].push_back(4);
    adjList[1].push_back(0);
    adjList[1].push_back(2);
    adjList[2].push_back(1);
    adjList[2].push_back(3);
    adjList[3].push_back(2);
    adjList[3].push_back(4);
    adjList[4].push_back(0);
    adjList[4].push_back(3);

    for (int i = 0; i < 5; i++) {
        std::cout << i << ": ";
        for (int friendNode : adjList[i]) {
            std::cout << friendNode << " ";
        }
        std::cout << std::endl;
    }

    // Output is printed above
    // Your code here
    return 0;
}

Hint

Run the program to see the adjacency list printed line by line.

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