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

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and density

↓

Use Adjacency List

↓

Less memory

↓

Efficient for

↓

iterating edges

↓

Graph operations optimized

Decide graph representation by size and density: use adjacency list for sparse graphs and adjacency matrix for dense graphs.

Execution Sample

DSA Go

graph := make([][]int, 3)
graph[0] = []int{1, 2}
graph[1] = []int{0}
graph[2] = []int{0}
// Adjacency List representation

This code creates an adjacency list for a graph with 3 nodes and edges from 0 to 1 and 2.

Execution Table

Step	Operation	Graph Size	Graph Density	Representation Chosen	Memory Usage	Visual State
1	Start with graph of 3 nodes	3 nodes	Unknown	None	N/A	{}
2	Check edges count: 2 edges	3 nodes	Sparse (2 edges < 3*2/2=3)	Adjacency List	Low	{0:[1,2],1:[0],2:[0]}
3	Build adjacency list	3 nodes	Sparse	Adjacency List	Low	{0:[1,2],1:[0],2:[0]}
4	Check if adjacency matrix better?	3 nodes	Sparse	No	High if matrix	Matrix would be 3x3 with mostly zeros
5	End	3 nodes	Sparse	Adjacency List	Low	{0:[1,2],1:[0],2:[0]}

💡 Graph is sparse, adjacency list chosen for memory and efficiency.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
graph size	3	3	3	3	3
edges count	0	2	2	2	2
graph density	unknown	sparse	sparse	sparse	sparse
representation	none	adjacency list	adjacency list	adjacency list	adjacency list
memory usage	N/A	low	low	high if matrix	low

Key Moments - 3 Insights

Why choose adjacency list for sparse graphs?

Because adjacency list stores only existing edges, saving memory as shown in execution_table step 2 and 3 where edges are few.

When is adjacency matrix better despite higher memory?

When graph is dense or you need to quickly check if an edge exists between two nodes, adjacency matrix offers O(1) lookup as noted in step 4.

How does graph density affect representation choice?

Density determines if edges are few or many; sparse means few edges favoring adjacency list, dense means many edges favoring matrix, as seen in variable_tracker 'graph density'.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what representation is chosen for the graph?

A Adjacency Matrix

B Adjacency List

C Edge List

D None

💡 Hint

Check the 'Representation Chosen' column at step 2 in execution_table.

At which step does the code confirm adjacency matrix is not better?

A Step 4

B Step 1

C Step 3

D Step 5

💡 Hint

Look for the step mentioning adjacency matrix evaluation in execution_table.

If the graph had many edges (dense), which representation would be preferred?

A Adjacency List

B Edge List

C Adjacency Matrix

D None

💡 Hint

Refer to concept_flow where dense graphs lead to adjacency matrix choice.

Concept Snapshot

Adjacency List vs Matrix:
- Use adjacency list for sparse graphs (few edges).
- Use adjacency matrix for dense graphs (many edges).
- List saves memory, matrix allows quick edge checks.
- Choose based on graph size and density.
- Lists store neighbors; matrices store all connections.

Full Transcript

This lesson shows how to choose between adjacency list and adjacency matrix to represent graphs. We start by checking the graph size and number of edges to determine density. Sparse graphs with few edges use adjacency lists to save memory by storing only existing edges. Dense graphs with many edges use adjacency matrices for quick edge lookup. The execution table traces steps deciding representation based on edges and density. Variable tracker shows how graph size, edges, density, and representation change during the process. Key moments clarify why lists suit sparse graphs and matrices suit dense graphs. The visual quiz tests understanding of representation choice at different steps. The snapshot summarizes when and why to use each representation.

Practice

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

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 nodes is called a sparse graph.

2. Step 2: Choose data structure for sparse graphs

   Adjacency lists store 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 graph? Use adjacency list 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 4 nodes in Go?

easy

A. var graph [4][4]int

B. graph := make([][]int, 4)

C. var graph []int

D. graph := map[int][]int{}

Solution

1. Step 1: Understand adjacency matrix declaration

   An adjacency matrix is a 2D fixed-size array representing edges between nodes.

2. Step 2: Check Go syntax for fixed 2D array

   "var graph [4][4]int" declares a 4x4 integer matrix correctly.

3. Final Answer:

   var graph [4][4]int -> Option A

4. Quick Check:

   Fixed 2D array = var graph [4][4]int [OK]

Hint: Adjacency matrix = fixed 2D array declaration [OK]

Common Mistakes:

• Using slice of slices without initialization for matrix
• Declaring 1D slice instead of 2D array
• Using map which is adjacency list style

3. Given the following Go code using an adjacency list, what will be printed?

graph := map[int][]int{
  0: {1, 2},
  1: {2},
  2: {0},
  3: {},
}
fmt.Println(graph[1])

medium

A. [0 2]

B. [2]

C. [1 2]

D. []

Solution

1. Step 1: Identify adjacency list entries for node 1

   Node 1 has edges to node 2 only, so graph[1] = {2}.

2. Step 2: Understand fmt.Println output

   Printing graph[1] outputs the slice [2].

3. Final Answer:

   [2] -> Option B

4. Quick Check:

   graph[1] = [2] [OK]

Hint: Print adjacency list for node key directly [OK]

Common Mistakes:

• Confusing keys and values in map
• Assuming node 1 connects to node 0
• Expecting adjacency matrix output

4. The following Go code attempts to create an adjacency matrix but has a bug. What is the bug?

graph := make([][]int, 3)
for i := range graph {
  graph[i] = make([]int, 3)
}
graph[0][1] = 1
graph[1][2] = 1
fmt.Println(graph[0][2])

medium

A. The matrix is not initialized properly

B. graph[0][2] should be 1 but prints 0

C. Index out of range error

D. No bug, code runs correctly

Solution

1. Step 1: Check matrix initialization

   Each row is initialized with make([]int, 3), so matrix is properly created.

2. Step 2: Check assigned values and print

   graph[0][1] and graph[1][2] are set to 1; graph[0][2] was never set, so prints 0.

3. Step 3: Verify no runtime errors

   All indices are within range; no errors occur.

4. Final Answer:

   No bug, code runs correctly -> Option D

5. Quick Check:

   Proper initialization and indexing = No bug [OK]

Hint: Check initialization and index ranges carefully [OK]

Common Mistakes:

• Assuming unassigned entries print 1
• Thinking initialization is missing
• Expecting index errors without out-of-range access

5. You need to represent a dense graph with 1000 nodes where you frequently check if an edge exists between any two nodes. Which data structure is best and why? A) Adjacency Matrix for constant-time edge checks B) Adjacency List for memory efficiency C) Edge List for simple iteration D) Map of maps for flexible keys

hard

A. Edge List for simple iteration

B. Adjacency List for memory efficiency

C. Adjacency Matrix for constant-time edge checks

D. Map of maps for flexible keys

Solution

1. Step 1: Understand graph density and operations

   A dense graph has many edges, close to the maximum possible.

2. Step 2: Choose data structure for fast edge existence checks

   Adjacency matrix allows O(1) time to check if edge exists between any two nodes.

3. Step 3: Consider memory tradeoff

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

4. Final Answer:

   Adjacency Matrix for constant-time edge checks -> Option C

5. Quick Check:

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

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

Common Mistakes:

• Choosing adjacency list for dense graphs slows edge checks
• Ignoring memory vs speed tradeoff
• Confusing edge list with adjacency matrix