Adjacency List vs Matrix When to Choose Which in DSA C++ - Visual Comparison

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph density

↓

Use Adjacency

↓

Efficient for

↓

Good for

Decide graph representation by checking if graph is sparse or dense; use adjacency list for sparse graphs and adjacency matrix for dense graphs.

Execution Sample

DSA C++

bool isEdge(int u, int v) {
  return adjMatrix[u][v] == 1;
}

// vs

bool isEdge(int u, int v) {
  for (int x : adjList[u]) {
    if (x == v) return true;
  }
  return false;
}

Check if edge exists between nodes u and v using adjacency matrix and adjacency list.

Execution Table

Step	Operation	Graph Type	Data Structure State	Pointer/Index Changes	Visual State
1	Start with empty graph	Adjacency List	adjList = [[], [], [], []]	head pointers at each node empty	0: [] 1: [] 2: [] 3: []
2	Add edge 0->1	Adjacency List	adjList = [[1], [], [], []]	Node 0 list updated	0: [1] 1: [] 2: [] 3: []
3	Add edge 0->2	Adjacency List	adjList = [[1, 2], [], [], []]	Node 0 list updated	0: [1, 2] 1: [] 2: [] 3: []
4	Add edge 1->2	Adjacency List	adjList = [[1, 2], [2], [], []]	Node 1 list updated	0: [1, 2] 1: [2] 2: [] 3: []
5	Check edge 0->2	Adjacency List	Traverse adjList[0]	Check elements 1, 2	Found 2 in list, edge exists
6	Start with empty graph	Adjacency Matrix	adjMatrix = 4x4 zero matrix	All indices zero	[[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]
7	Add edge 0->1	Adjacency Matrix	adjMatrix[0][1] = 1	Set matrix[0][1]	[[0,1,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]
8	Add edge 0->2	Adjacency Matrix	adjMatrix[0][2] = 1	Set matrix[0][2]	[[0,1,1,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]
9	Add edge 1->2	Adjacency Matrix	adjMatrix[1][2] = 1	Set matrix[1][2]	[[0,1,1,0], [0,0,1,0], [0,0,0,0], [0,0,0,0]]
10	Check edge 0->2	Adjacency Matrix	Check adjMatrix[0][2]	Value is 1	Edge exists
11	Check edge 2->3	Adjacency Matrix	Check adjMatrix[2][3]	Value is 0	Edge does not exist
12	Check edge 0->3	Adjacency List	Traverse adjList[0]	Check elements 1, 2	Edge does not exist
13	End	Both	No more operations	N/A	Execution complete

💡 All edges added and checked; traversal and lookups complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	Final
adjList	[[],[],[],[]]	[[1],[],[],[]]	[[1, 2],[],[],[]]	[[1, 2],[2],[],[]]	[[1, 2],[2],[],[]]	N/A	N/A	N/A	N/A	N/A	N/A	[[1, 2],[2],[],[]]	[[1, 2],[2],[],[]]
adjMatrix	N/A	N/A	N/A	N/A	N/A	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,1,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	[[0,1,1,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	[[0,1,1,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]	N/A	[[0,1,1,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]

Key Moments - 3 Insights

Why does adjacency list use less space for sparse graphs?

Because adjacency list stores only existing edges, as shown in steps 2-4, it keeps lists small. The matrix (steps 6-9) stores all possible edges, using more space even if many are zero.

Why is checking edge existence faster in adjacency matrix?

In adjacency matrix (steps 10-11), checking edge is a direct index lookup (O(1)). In adjacency list (step 5), it requires scanning the list which can take longer if many edges exist.

When is adjacency matrix preferred despite higher space?

When graph is dense or quick edge checks are needed, adjacency matrix is preferred as it provides constant time edge lookup, shown in steps 6-11.

Visual Quiz - 3 Questions

Look at the execution table at step 5, what edge is being checked in the adjacency list?

A Edge 1->2

B Edge 2->3

C Edge 0->2

D Edge 0->1

💡 Hint

Check the 'Operation' and 'Visual State' columns at step 5 in the execution table.

At which step does the adjacency matrix first show an edge from node 1 to node 2?

A Step 7

B Step 9

C Step 8

D Step 10

💡 Hint

Look at the 'Add edge 1->2' operation in the execution table under adjacency matrix.

If the graph had 1000 nodes but only 10 edges, which data structure would save more memory?

A Adjacency List

B Adjacency Matrix

C Both use same memory

D Depends on edge weights

💡 Hint

Refer to the key moment about space usage and the variable_tracker showing sparse graph storage.

Concept Snapshot

Adjacency List vs Matrix:
- Use adjacency list for sparse graphs (few edges).
- Use adjacency matrix for dense graphs (many edges).
- List stores edges only, saving space.
- Matrix allows O(1) edge checks but uses more memory.
- Choose based on graph size and edge density.

Full Transcript

This visual execution compares adjacency list and adjacency matrix graph representations. We start with empty graphs and add edges step-by-step. The adjacency list stores edges as lists per node, using less space for sparse graphs. The adjacency matrix uses a 2D array marking edges, allowing quick edge checks but using more memory. We trace adding edges and checking their existence in both structures. Key moments highlight why adjacency list is space efficient for sparse graphs and why matrix is faster for edge lookups. The choice depends on graph density and operation needs.

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