Adjacency List vs Matrix When to Choose Which in DSA C++ - Build Both Approaches

Adjacency List vs Matrix: When to Choose Which

📖 Scenario: Imagine you are helping a city planner represent the roads between different neighborhoods. Each neighborhood is a point (node), and roads are connections (edges) between them. You want to store this information in a way that is easy to check if two neighborhoods are connected and to add new roads.

🎯 Goal: You will create two ways to represent the city roads: an adjacency list and an adjacency matrix. Then, you will compare them by printing their contents. This will help you understand when to use each method.

📋 What You'll Learn

Create an adjacency list for a graph with 4 neighborhoods and these roads: 0-1, 0-2, 1-2, 2-3

Create an adjacency matrix for the same graph

Print both the adjacency list and adjacency matrix

Understand the difference in storage and access between the two

💡 Why This Matters

🌍 Real World

City planners, network engineers, and game developers use graph representations to model connections between points like roads, computers, or game levels.

💼 Career

Understanding adjacency lists and matrices helps in roles involving network design, route planning, and algorithm optimization.

1

Create the adjacency list

Create a variable called adjList as a vector of vectors of integers with size 4. Add the roads as edges: add 1 and 2 to adjList[0], add 0 and 2 to adjList[1], add 0, 1, and 3 to adjList[2], and add 2 to adjList[3].

DSA C++

#include 
#include 

int main() {

    // Create adjacency list with 4 nodes
    // Your code here

    return 0;
}

Hint

Use std::vector> adjList(4); to create the list. Then use push_back to add neighbors.

2

Create the adjacency matrix

Create a variable called adjMatrix as a 4x4 vector of integers initialized with 0. Then set the value to 1 for each road: set adjMatrix[0][1] and adjMatrix[1][0] to 1, adjMatrix[0][2] and adjMatrix[2][0] to 1, adjMatrix[1][2] and adjMatrix[2][1] to 1, and adjMatrix[2][3] and adjMatrix[3][2] to 1.

DSA C++

#include 
#include 

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

    // Create adjacency matrix 4x4 initialized with 0
    // Your code here

    return 0;
}

Hint

Use std::vector> adjMatrix(4, std::vector(4, 0)); to create the matrix. Then set the connected pairs to 1.

3

Print the adjacency list

Use a for loop with variable i from 0 to 3 to print each node's neighbors from adjList. Inside, use another for loop with variable neighbor to print each neighbor. Print the format: Node i: neighbor1 neighbor2 ....

DSA C++

#include 
#include 

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

    std::vector> adjMatrix(4, std::vector(4, 0));
    adjMatrix[0][1] = 1;
    adjMatrix[1][0] = 1;
    adjMatrix[0][2] = 1;
    adjMatrix[2][0] = 1;
    adjMatrix[1][2] = 1;
    adjMatrix[2][1] = 1;
    adjMatrix[2][3] = 1;
    adjMatrix[3][2] = 1;

    // Print adjacency list
    // Your code here

    return 0;
}

Hint

Use nested loops: outer loop from 0 to 3, inner loop over adjList[i]. Print neighbors separated by spaces.

4

Print the adjacency matrix

Use two nested for loops with variables i and j from 0 to 3 to print the adjMatrix. Print each row on a new line with values separated by spaces.

DSA C++

#include 
#include 

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

    std::vector> adjMatrix(4, std::vector(4, 0));
    adjMatrix[0][1] = 1;
    adjMatrix[1][0] = 1;
    adjMatrix[0][2] = 1;
    adjMatrix[2][0] = 1;
    adjMatrix[1][2] = 1;
    adjMatrix[2][1] = 1;
    adjMatrix[2][3] = 1;
    adjMatrix[3][2] = 1;

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

    // Print adjacency matrix
    // Your code here

    return 0;
}

Hint

Use nested loops from 0 to 3 for rows and columns. Print each value followed by a space. Print a newline after each row.

Practice

1. Which data structure is generally better for representing a graph with very few edges compared to the number of vertices?

easy

A. Adjacency List

B. Adjacency Matrix

C. Edge List

D. Incidence Matrix

Solution

1. Step 1: Understand graph density

   A graph with very few edges compared to vertices is called a sparse graph.

2. Step 2: Choose efficient representation for sparse graphs

   Adjacency List stores only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graphs use adjacency lists for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing edge list with adjacency matrix
• Assuming adjacency matrix is always better

2. Which of the following is the correct way to declare an adjacency matrix for a graph with 5 vertices in C++?

easy

A. int graph[5][5];

B. vector graph(5, vector<int>(5));

C. vector<int> graph(5);

D. int graph[5];

Solution

1. Step 1: Understand adjacency matrix structure

   An adjacency matrix is a 2D structure with size V x V for V vertices.

2. Step 2: Choose correct C++ declaration

   Using vector of vectors initializes a 5x5 matrix properly.

3. Final Answer:

   vector graph(5, vector<int>(5)); -> Option B

4. Quick Check:

   2D vector for adjacency matrix = vector graph(5, vector<int>(5)); [OK]

Hint: Adjacency matrix needs 2D structure, use vector [OK]

Common Mistakes:

• Using 1D array for adjacency matrix
• Not initializing inner vectors
• Confusing adjacency list syntax with matrix

3. Consider the following C++ code snippet for a graph with 3 vertices using adjacency list:

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

What is the output of this code?

medium

A. 0: 1 2
1: 0
2:

B. 0: 2
1: 0
2: 1

C. 0: 1
1: 2
2: 0

D. 0:
1: 2
2: 0 1

Solution

1. Step 1: Trace adjacency list insertions

   adj[0] has 1, adj[1] has 2, adj[2] has 0.

2. Step 2: Print adjacency list contents

   Loop prints each vertex and its adjacency: 0:1, 1:2, 2:0.

3. Final Answer:

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

4. Quick Check:

   Adjacency list print matches 0: 1 1: 2 2: 0 [OK]

Hint: Follow push_back calls to trace adjacency list output [OK]

Common Mistakes:

• Mixing up indices and values
• Assuming adjacency matrix output
• Forgetting to print spaces or newlines correctly

4. The following code attempts to create an adjacency matrix for a graph with 4 vertices but has a bug:

int graph[4][4];
for (int i = 0; i <= 4; i++) {
    for (int j = 0; j <= 4; j++) {
        graph[i][j] = 0;
    }
}

What is the main issue in this code?

medium

A. The inner loop should start from 1 instead of 0

B. The matrix is not initialized to zero

C. The graph size should be 5 instead of 4

D. The loops use <= causing out-of-bounds access

Solution

1. Step 1: Analyze loop bounds

   Loops run from 0 to 4 inclusive, which means 5 iterations each.

2. Step 2: Check array size and access

   Array size is 4x4, valid indices are 0 to 3. Index 4 causes out-of-bounds error.

3. Final Answer:

   The loops use <= causing out-of-bounds access -> Option D

4. Quick Check:

   Loop bounds exceed array size causing error [OK]

Hint: Use < instead of <= for array indices [OK]

Common Mistakes:

• Assuming array size is 5
• Thinking initialization is missing
• Changing loop start instead of end condition

5. You have a graph with 1000 vertices and about 10,000 edges. You need to perform frequent edge existence checks (i.e., is there an edge between vertex u and v?). Which representation is best and why? Choose the best option.

hard

A. Adjacency Matrix, because it allows O(1) edge existence checks despite higher space

B. Adjacency List, because it uses less space and edge checks are O(1)

C. Edge List, because it is simplest and fastest for edge checks

D. Adjacency Matrix, because it uses less space for sparse graphs

Solution

1. Step 1: Understand graph size and density

   1000 vertices and 10,000 edges is a sparse graph but with many edges.

2. Step 2: Compare edge existence check times

   Adjacency matrix allows O(1) edge check by direct index access; adjacency list requires searching neighbors.

3. Step 3: Consider space vs speed tradeoff

   Matrix uses more space but is faster for edge queries, which is needed here.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks despite higher space -> Option A

5. Quick Check:

   Fast edge check needs adjacency matrix [OK]

Hint: For fast edge checks, adjacency matrix is best despite space [OK]

Common Mistakes:

• Assuming adjacency list gives O(1) edge checks
• Choosing edge list for fast queries
• Ignoring space vs time tradeoff