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

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and edges

↓

Use List

↓

Less space

↓

Slower edge check

↓

Good for large graphs

↓

End

Decide graph representation by checking if graph is sparse or dense, then choose adjacency list or matrix accordingly.

Execution Sample

DSA Typescript

const graphList = new Map<number, number[]>();
graphList.set(1, [2,3]);
graphList.set(2, [1]);
graphList.set(3, [1]);

const graphMatrix = [
  [0,1,1],
  [1,0,0],
  [1,0,0]
];

Shows a simple graph with 3 nodes represented as adjacency list and adjacency matrix.

Execution Table

Step	Operation	Graph Type	Data Structure State	Memory Use	Edge Check Speed	Visual State
1	Initialize graph with 3 nodes and 2 edges	Adjacency List	{1: [2,3], 2: [1], 3: [1]}	Low (O(V+E))	Slower (need to search lists)	1 -> 2,3; 2 -> 1; 3 -> 1
2	Initialize graph with 3 nodes and 2 edges	Adjacency Matrix	[[0,1,1],[1,0,0],[1,0,0]]	Higher (O(V^2))	Faster (direct index)	1 2 3 1 0 1 1 2 1 0 0 3 1 0 0
3	Check if edge exists between 1 and 3	Adjacency List	Same	Same	Search list of node 1	Check if 3 in [2,3] → Yes
4	Check if edge exists between 1 and 3	Adjacency Matrix	Same	Same	Direct access matrix[0][2]	Value is 1 → Yes
5	Add edge between 2 and 3	Adjacency List	{1: [2,3], 2: [1,3], 3: [1,2]}	Low	Slower	1 -> 2,3; 2 -> 1,3; 3 -> 1,2
6	Add edge between 2 and 3	Adjacency Matrix	[[0,1,1],[1,0,1],[1,1,0]]	Higher	Faster	1 2 3 1 0 1 1 2 1 0 1 3 1 1 0
7	Decide representation for large sparse graph	Decision	Prefer adjacency list	Efficient	Acceptable	Use list for less memory
8	Decide representation for small dense graph	Decision	Prefer adjacency matrix	Memory not a problem	Fast edge checks	Use matrix for speed
9	End	N/A	N/A	N/A	N/A	Representation chosen based on graph type

💡 Stop after deciding best representation based on graph size and density

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 6	Final
graphList	empty Map	{1:[2,3],2:[1],3:[1]}	{1:[2,3],2:[1],3:[1]}	{1:[2,3],2:[1,3],3:[1,2]}	{1:[2,3],2:[1,3],3:[1,2]}	{1:[2,3],2:[1,3],3:[1,2]}
graphMatrix	empty array	N/A	[[0,1,1],[1,0,0],[1,0,0]]	[[0,1,1],[1,0,0],[1,0,0]]	[[0,1,1],[1,0,1],[1,1,0]]	[[0,1,1],[1,0,1],[1,1,0]]

Key Moments - 3 Insights

Why does adjacency list use less memory for sparse graphs?

Because adjacency list stores only existing edges, as shown in step 1 and 5 in execution_table, it uses memory proportional to vertices plus edges (O(V+E)), unlike matrix which uses O(V^2) regardless.

Why is edge check faster in adjacency matrix?

In step 4 and 6, adjacency matrix allows direct access to check if edge exists using indices, making it O(1), while adjacency list requires searching the list which is slower.

When should we prefer adjacency matrix despite higher memory?

As in step 8, for small dense graphs where memory is not a big concern, adjacency matrix is preferred for its fast edge lookup and simpler implementation.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the method used to check edge between nodes 1 and 3 in adjacency list?

A Direct index access in matrix

B Search node 1's adjacency list for 3

C Check all nodes for edge

D Use a boolean matrix

💡 Hint

Refer to execution_table row 3 under 'Edge Check Speed' and 'Visual State'

At which step does adjacency matrix add an edge between nodes 2 and 3?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Check execution_table rows 5 and 6 for adjacency matrix updates

If the graph is very large but has few edges, which representation is better according to variable_tracker?

A Both are equally good

B Adjacency matrix for fast edge checks

C Adjacency list for memory efficiency

D Neither can represent large graphs

💡 Hint

Look at variable_tracker rows for graphList and graphMatrix memory usage

Concept Snapshot

Adjacency List vs Matrix:
- List stores edges as lists per node, uses less memory for sparse graphs
- Matrix uses 2D array, uses more memory but allows O(1) edge checks
- Choose list for large, sparse graphs
- Choose matrix for small, dense graphs
- Edge addition and checks differ in speed and memory use

Full Transcript

This concept compares adjacency list and adjacency matrix for graph representation. Adjacency list stores neighbors in lists, saving memory for sparse graphs but making edge checks slower. Adjacency matrix uses a 2D array, consuming more memory but allowing fast edge checks. The choice depends on graph size and density: use list for large sparse graphs and matrix for small dense graphs. The execution table shows step-by-step how edges are added and checked in both structures, and the variable tracker shows memory and state changes. Key moments clarify why memory and speed differ and when to prefer each structure.

Practice

1. Which data structure is generally more space-efficient 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

   Sparse graphs have few edges compared to vertices, so storing all possible edges wastes space.

2. Step 2: Compare space usage of adjacency list and matrix

   Adjacency list stores only existing edges, using less space for sparse graphs. Adjacency matrix always uses space for all possible edges.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graph? Use adjacency list for less space [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs
• Confusing edge count with vertex count
• Ignoring space complexity differences

2. Which of the following is the correct TypeScript syntax to declare an adjacency matrix for a graph with 3 vertices initialized with zeros?

easy

A. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0));

B. const matrix: number[] = [0,0,0];

C. const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]];

D. const matrix: number[][] = Array(3).map(() => Array(3).fill(0));

Solution

1. Step 1: Understand adjacency matrix type

   An adjacency matrix is a 2D array (array of arrays) of numbers representing edges.

2. Step 2: Check initialization correctness

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; explicitly creates a 3x3 matrix with zeros. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0)); uses fill with the same inner array reference, causing bugs. const matrix: number[][] = Array(3).map(() => Array(3).fill(0)); uses map on empty array, which won't work as expected. const matrix: number[] = [0,0,0]; is 1D array, not matrix.

3. Final Answer:

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; -> Option C

4. Quick Check:

   Explicit 2D array with zeros = const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; [OK]

Hint: Use explicit 2D array for adjacency matrix initialization [OK]

Common Mistakes:

• Using fill with nested arrays causing shared references
• Declaring 1D array instead of 2D
• Using map on empty array without initialization

3. Given the following adjacency list representation of a graph in TypeScript:

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: []
};
console.log(graph[2]);

What will be the output?

medium

A. [2]

B. [1, 2]

C. undefined

D. [0, 3]

Solution

1. Step 1: Identify the adjacency list for vertex 2

   In the graph object, key '2' maps to the array [0, 3].

2. Step 2: Understand console.log output

   Logging graph[2] prints the array [0, 3] representing edges from vertex 2.

3. Final Answer:

   [0, 3] -> Option D

4. Quick Check:

   graph[2] = [0, 3] [OK]

Hint: Access adjacency list by vertex key to get connected nodes [OK]

Common Mistakes:

• Confusing keys and values in adjacency list
• Expecting adjacency matrix output
• Assuming undefined for existing keys

4. Consider this TypeScript code snippet for creating an adjacency matrix for a graph with 3 vertices:

const size = 3;
const matrix = new Array(size).fill(new Array(size).fill(0));
matrix[0][1] = 1;
console.log(matrix);

What is the problem with this code?

medium

A. All rows refer to the same inner array, so all rows change when one element changes

B. The matrix is not initialized with zeros

C. The matrix is not a 2D array

D. The size variable is not used correctly

Solution

1. Step 1: Analyze the fill method usage

   Using fill with new Array(size).fill(0) creates one inner array and fills outer array with references to the same inner array.

2. Step 2: Understand effect of modifying one element

   Changing matrix[0][1] changes that element in all rows because they share the same inner array reference.

3. Final Answer:

   All rows refer to the same inner array, so all rows change when one element changes -> Option A

4. Quick Check:

   Shared inner array reference causes unexpected changes [OK]

Hint: Avoid fill with nested arrays; use map to create separate arrays [OK]

Common Mistakes:

• Thinking fill creates separate inner arrays
• Ignoring shared reference problem
• Assuming matrix is 1D array

5. You need to represent a dense graph with 1000 vertices where you frequently check if an edge exists between any two vertices. Which representation is best and why?

hard

A. Adjacency List, because it uses less space for dense graphs

B. Adjacency Matrix, because it allows O(1) edge existence checks

C. Edge List, because it is fastest for dense graphs

D. Incidence Matrix, because it uses less space than adjacency matrix

Solution

1. Step 1: Understand graph density and operation needs

   Dense graph means many edges; checking edge existence frequently requires fast lookup.

2. Step 2: Compare adjacency list and matrix for edge checks

   Adjacency matrix allows direct O(1) access to check if edge exists between two vertices. Adjacency list requires searching neighbors, which can be slower in dense graphs.

3. Step 3: Consider space tradeoff

   Though adjacency matrix uses more space, for dense graphs this is acceptable and beneficial for speed.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks -> Option B

5. Quick Check:

   Dense graph + frequent edge check = Adjacency Matrix [OK]

Hint: Dense graph + frequent edge check? Use adjacency matrix [OK]

Common Mistakes:

• Choosing adjacency list for dense graphs needing fast edge checks
• Ignoring time complexity of edge existence queries
• Confusing edge list with adjacency matrix benefits