Adjacency List Representation in DSA C - Execution Trace

Concept Flow - Adjacency List Representation

Start

↓

Create array of lists

↓

For each edge

↓

Add neighbor to source list

↓

Add neighbor to destination list (if undirected)

↓

Repeat for all edges

↓

Graph represented as adjacency lists

↓

End

Build an array where each index holds a list of neighbors for that vertex, adding edges step-by-step.

Execution Sample

DSA C

Node* graph[4];
// graph as array of lists
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 2);
addEdge(2, 3);

Create adjacency lists for a graph with 4 vertices and add edges between them.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize graph with 4 empty lists	0: [] 1: [] 2: [] 3: []	graph array created	0: null 1: null 2: null 3: null
2	Add edge 0 -> 1	0: [1] 1: [] 2: [] 3: []	Add node 1 to list at index 0	0: 1 -> null 1: null 2: null 3: null
3	Add edge 0 -> 2	0: [2,1] 1: [] 2: [] 3: []	Add node 2 at head of list 0	0: 2 -> 1 -> null 1: null 2: null 3: null
4	Add edge 1 -> 2	0: [2,1] 1: [2] 2: [] 3: []	Add node 2 to list at index 1	0: 2 -> 1 -> null 1: 2 -> null 2: null 3: null
5	Add edge 2 -> 3	0: [2,1] 1: [2] 2: [3] 3: []	Add node 3 to list at index 2	0: 2 -> 1 -> null 1: 2 -> null 2: 3 -> null 3: null
6	End	Graph fully built	No changes	0: 2 -> 1 -> null 1: 2 -> null 2: 3 -> null 3: null

💡 All edges processed, adjacency lists complete

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
graph[0]	null	1 -> null	2 -> 1 -> null	2 -> 1 -> null	2 -> 1 -> null	2 -> 1 -> null
graph[1]	null	null	null	2 -> null	2 -> null	2 -> null
graph[2]	null	null	null	null	3 -> null	3 -> null
graph[3]	null	null	null	null	null	null

Key Moments - 3 Insights

Why does the list at graph[0] show 2 before 1 after adding edge 0->2?

Because new nodes are added at the head of the list, so 2 is inserted before 1, as shown in step 3 of execution_table.

Why is graph[3] still empty after all edges?

No edges start from vertex 3, so its adjacency list remains empty, as seen in the final visual state.

Why do we add neighbors only to the source vertex's list?

Because this example shows a directed graph; edges go one way, so only source lists get updated, as shown in each addEdge operation.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the order of nodes in graph[0]'s list?

A 2 -> 1 -> null

B 1 -> 2 -> null

C null

D 1 -> null

💡 Hint

Check the Visual State column at step 3 in execution_table

At which step does graph[1] first get a neighbor added?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the Nodes in List column for graph[1] in execution_table

If we add edge 3 -> 0, how would graph[3]'s list change?

A It would become 3 -> null

B It would remain null

C It would become 0 -> null

D It would become 1 -> null

💡 Hint

Adding edge 3->0 adds 0 to graph[3]'s adjacency list

Concept Snapshot

Adjacency List Representation:
- Use an array where each index is a vertex.
- Each array element holds a linked list of neighbors.
- Add edges by inserting neighbors in source vertex's list.
- Efficient for sparse graphs.
- Directed edges update only source list.
- Visual: graph[0]: 2 -> 1 -> null means vertex 0 connects to 2 and 1.

Full Transcript

Adjacency List Representation stores graph edges as lists for each vertex. We start with an array of empty lists. For each edge, we add the destination vertex to the source vertex's list. This example shows a directed graph with 4 vertices. Edges are added step-by-step, updating the lists. The lists grow by adding new nodes at the head. The final structure shows which vertices connect to which neighbors. This method is memory efficient for graphs with fewer edges.