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 size and edges

↓

Few edges, large nodes

→Use Adjacency List

↓

Many edges, dense graph

→Use Adjacency Matrix

↓

Implement chosen structure

↓

Perform graph operations efficiently

Decide graph representation by checking graph density: sparse graphs use adjacency lists, dense graphs use adjacency matrices.

Execution Sample

DSA C

/* Adjacency List for sparse graph */
struct Node {
  int vertex;
  struct Node* next;
};

/* Adjacency Matrix for dense graph */
int matrix[MAX][MAX];

Shows basic declarations for adjacency list and matrix representations.

Execution Table

Step	Operation	Graph Type	Data Structure State	Visual State
1	Start with 5 nodes, 4 edges	Sparse	Adjacency List empty	[] [] [] [] []
2	Add edge 0->1	Sparse	List[0]: 1 -> NULL	[0:1] [] [] [] []
3	Add edge 0->4	Sparse	List[0]: 4 -> 1 -> NULL	[0:4->1] [] [] [] []
4	Add edge 1->2	Sparse	List[1]: 2 -> NULL	[0:4->1] [1:2] [] [] []
5	Add edge 3->4	Sparse	List[3]: 4 -> NULL	[0:4->1] [1:2] [] [3:4] []
6	Check if edge 0->3 exists	Sparse	Traverse List[0]	No edge found
7	Start with 5 nodes, dense graph	Dense	Matrix all zeros	[[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
8	Add edge 0->1	Dense	Matrix[0][1] = 1	[[0,1,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
9	Add edge 0->4	Dense	Matrix[0][4] = 1	[[0,1,0,0,1], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
10	Add edge 1->2	Dense	Matrix[1][2] = 1	[[0,1,0,0,1], [0,0,1,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
11	Add edge 3->4	Dense	Matrix[3][4] = 1	[[0,1,0,0,1], [0,0,1,0,0], [0,0,0,0,0], [0,0,0,0,1], [0,0,0,0,0]]
12	Check if edge 0->3 exists	Dense	Check Matrix[0][3]	Value = 0, no edge
13	End	-	-	Representation chosen based on graph density

💡 Execution stops after graph is represented and edge checks are done.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	Final
Adjacency List	Empty lists	[0:1]	[0:4->1]	[0:4->1, 1:2]	[0:4->1, 1:2, 3:4]	[No edge 0->3]	-	-	-	-	-	Final sparse graph lists
Adjacency Matrix	All zeros	-	-	-	-	-	[0][1]=1	[0][4]=1	[1][2]=1	[3][4]=1	[0][3]=0 no edge	Final dense graph matrix

Key Moments - 3 Insights

Why use adjacency list for sparse graphs instead of matrix?

Adjacency list stores only existing edges, saving memory and speeding traversal, as shown in steps 2-5 where only edges are stored. Matrix would waste space with many zeros.

Why is adjacency matrix better for dense graphs?

Matrix allows quick edge checks in O(1) time, as seen in steps 8-12. For dense graphs with many edges, this is efficient despite higher memory use.

How to check if an edge exists in adjacency list vs matrix?

In adjacency list (step 6), we traverse the list for the node. In matrix (step 12), we directly check the matrix cell for 1 or 0.

Visual Quiz - 3 Questions

Look at the execution table, what is the adjacency list state after step 3?

A [0:4->1]

B [1:2]

C [0:1]

D Empty lists

💡 Hint

Check the 'Data Structure State' column at step 3 in execution_table.

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

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look at the 'Operation' and 'Data Structure State' columns for matrix updates.

If the graph had very few edges but many nodes, which representation is best?

A Adjacency Matrix

B Adjacency List

C Both are equally good

D Neither is suitable

💡 Hint

Refer to the concept_flow and key_moments about sparse graphs.

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 fast edge checks
- List stores neighbors as linked nodes
- Matrix uses 2D array with 1/0 for edges

Full Transcript

This concept compares adjacency list and adjacency matrix for graph representation. The choice depends on graph 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 fast edge lookup. The execution table shows step-by-step how edges are added and checked in both structures. Key moments clarify why each structure suits different graph types and how edge existence is checked. The visual quiz tests understanding of states and steps in the execution. The snapshot summarizes when and why to choose each representation.