Adjacency List Representation in DSA Go - Execution Trace

Concept Flow - Adjacency List Representation

Start

↓

Create empty adjacency list

↓

For each edge (u,v)

↓

Add v to u's list

↓

Add u to v's list (if undirected)

↓

Repeat for all edges

↓

Adjacency list ready

Build adjacency list by adding each edge's nodes to each other's lists for undirected graphs.

Execution Sample

DSA Go

edges := [][]int{{0,1},{0,2},{1,2},{2,3}}
adjList := make([][]int, 4)
for _, e := range edges {
  u, v := e[0], e[1]
  adjList[u] = append(adjList[u], v)
  adjList[v] = append(adjList[v], u)
}

Creates adjacency list for a graph with 4 nodes and edges between them.

Execution Table

Step	Operation	Edge Processed	Adjacency List State	Pointer Changes	Visual State
1	Initialize adjacency list	None	[[], [], [], []]	adjList created with 4 empty slices	0: [] 1: [] 2: [] 3: []
2	Process edge	[0,1]	[[1], [0], [], []]	adjList[0] append 1, adjList[1] append 0	0: [1] 1: [0] 2: [] 3: []
3	Process edge	[0,2]	[[1,2], [0], [0], []]	adjList[0] append 2, adjList[2] append 0	0: [1,2] 1: [0] 2: [0] 3: []
4	Process edge	[1,2]	[[1,2], [0,2], [0,1], []]	adjList[1] append 2, adjList[2] append 1	0: [1,2] 1: [0,2] 2: [0,1] 3: []
5	Process edge	[2,3]	[[1,2], [0,2], [0,1,3], [2]]	adjList[2] append 3, adjList[3] append 2	0: [1,2] 1: [0,2] 2: [0,1,3] 3: [2]
6	All edges processed	None	[[1,2], [0,2], [0,1,3], [2]]	No changes	0: [1,2] 1: [0,2] 2: [0,1,3] 3: [2]

💡 All edges processed, adjacency list fully built.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
adjList[0]	[]	[1]	[1,2]	[1,2]	[1,2]	[1,2]
adjList[1]	[]	[0]	[0]	[0,2]	[0,2]	[0,2]
adjList[2]	[]	[]	[0]	[0,1]	[0,1,3]	[0,1,3]
adjList[3]	[]	[]	[]	[]	[2]	[2]

Key Moments - 3 Insights

Why do we add each node to the other's list in an undirected graph?

Because edges connect nodes both ways, so adjacency lists must reflect neighbors for both nodes, as shown in steps 2-5 where both adjList[u] and adjList[v] are updated.

What happens if the graph is directed? Do we add both ways?

No, for directed graphs, we only add v to u's list (adjList[u]) and skip adding u to v's list. This differs from the undirected case shown in the execution table.

Why do we initialize the adjacency list with empty slices for each node?

To prepare a place to store neighbors for each node before adding edges, as seen in step 1 where adjList is created with empty slices.

Visual Quiz - 3 Questions

Look at the execution table, what is adjList[2] after processing edge [1,2] (step 4)?

A [0,1]

B [0]

C [1,3]

D [0,1,3]

💡 Hint

Check the 'Adjacency List State' column at step 4 in the execution table.

At which step does adjList[3] first get updated?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for when adjList[3] changes from empty to non-empty in the variable tracker and execution table.

If the graph were directed, which operation would be skipped?

A Adding v to u's list

B Adding u to v's list

C Initializing adjacency list

D Processing edges

💡 Hint

Refer to key moment 2 about directed vs undirected graph edge additions.

Concept Snapshot

Adjacency List Representation:
- Use a list of lists to store neighbors for each node.
- For each edge (u,v), add v to u's list.
- For undirected graphs, also add u to v's list.
- Efficient for sparse graphs.
- Initialize with empty lists for all nodes.

Full Transcript

Adjacency List Representation builds a graph by storing neighbors for each node in a list. We start with an empty list for each node. For every edge, we add the connected nodes to each other's lists if the graph is undirected. This creates a structure where each node points to its neighbors. The example code processes edges step-by-step, updating the adjacency list. Key points include adding both directions for undirected graphs and initializing empty lists before adding edges. The final adjacency list shows neighbors for all nodes.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A matrix showing distances between nodes

B. A list where each node stores its connected neighbors

C. A list of all nodes without connections

D. A stack of nodes visited during traversal

Solution

1. Step 1: Understand adjacency list concept and compare options

   An adjacency list stores each node with a list of its neighbors, showing direct connections. Only the description "A list where each node stores its connected neighbors" correctly describes this structure; others describe different concepts.

2. Final Answer:

   A list where each node stores its connected neighbors -> Option B

3. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always stores neighbors per node [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking adjacency list stores distances
• Mixing adjacency list with traversal order

2. Which Go syntax correctly declares an adjacency list for a graph with integer nodes?

easy

A. var graph map[int][]int = make(map[int][]int)

B. var graph []int = make([]int, 0)

C. var graph map[int]int = make(map[int]int)

D. var graph [][]int = make([][]int, 0)

Solution

1. Step 1: Identify adjacency list type in Go and check options for correct syntax

   An adjacency list maps each node (int) to a slice of connected nodes ([]int), so map[int][]int is correct. var graph map[int][]int = make(map[int][]int) uses map[int][]int with make, which is correct. Others use wrong types or slices without mapping.

2. Final Answer:

   var graph map[int][]int = make(map[int][]int) -> Option A

3. Quick Check:

   Adjacency list = map node to slice [OK]

Hint: Adjacency list in Go = map[node][]neighbors [OK]

Common Mistakes:

• Using slice of ints instead of map for adjacency list
• Declaring map[int]int which stores single int, not neighbors
• Confusing slice of slices with map

3. Given the following Go code, what is the printed adjacency list?

graph := make(map[int][]int)
graph[1] = []int{2, 3}
graph[2] = []int{1}
graph[3] = []int{1, 4}
graph[4] = []int{3}

for node, neighbors := range graph {
    fmt.Printf("%d -> %v\n", node, neighbors)
}

medium

A. 1 -> [2 3]
2 -> [1]
3 -> [1 4]
4 -> [3]

B. 1 -> [1 4]
2 -> [2 3]
3 -> [3]
4 -> [4]

C. 1 -> [2]
2 -> [3]
3 -> [4]
4 -> [1]

D. 1 -> []
2 -> []
3 -> []
4 -> []

Solution

1. Step 1: Analyze graph assignments and match printed output

   Node 1 connects to 2 and 3, node 2 connects to 1, node 3 connects to 1 and 4, node 4 connects to 3. Output prints each node with its neighbors slice exactly as assigned, matching 1 -> [2 3]\n2 -> [1]\n3 -> [1 4]\n4 -> [3].

2. Final Answer:

   1 -> [2 3] 2 -> [1] 3 -> [1 4] 4 -> [3] -> Option A

3. Quick Check:

   Print adjacency list as assigned [OK]

Hint: Print adjacency list shows node and its neighbors slice [OK]

Common Mistakes:

• Mixing neighbors between nodes
• Confusing slice contents order
• Assuming empty neighbors incorrectly

4. Identify the error in this Go code snippet for adding an edge to an undirected graph adjacency list:

func addEdge(graph map[int][]int, u int, v int) {
    graph[u] = append(graph[u], v)
    graph[v] = append(graph[u], v)
}

medium

A. append cannot be used with slices

B. Function does not return the updated graph

C. map[int][]int cannot be modified inside function

D. Second append uses graph[u] instead of graph[v]

Solution

1. Step 1: Review append calls for edges and identify correct usage

   First append adds v to graph[u], correct. Second append should add u to graph[v], but uses graph[u] mistakenly. Second append must be graph[v] = append(graph[v], u) to add reverse edge for undirected graph.

2. Final Answer:

   Second append uses graph[u] instead of graph[v] -> Option D

3. Quick Check:

   Append neighbors to correct node slice [OK]

Hint: Append neighbors to correct node slice for undirected edges [OK]

Common Mistakes:

• Appending to wrong slice causing incorrect graph
• Thinking map cannot be modified inside function
• Misunderstanding append usage in Go

5. You have a graph represented by an adjacency list in Go as map[int][]int. How would you efficiently check if an edge exists between nodes u and v?

hard

A. Iterate over graph[u] slice to find v; return true if found, else false

B. Check if graph[u][v] exists directly using indexing

C. Use a map[int]bool inside graph[u] for constant time lookup

D. Sort graph[u] slice and use binary search to find v

Solution

1. Step 1: Understand adjacency list lookup and optimize lookup with map

   graph[u] is a slice, so direct indexing by v is invalid (Check if graph[u][v] exists directly using indexing wrong). Iteration (Iterate over graph[u] slice to find v; return true if found, else false) is linear time. Using map[int]bool inside graph[u] allows constant time check if v is neighbor (Use a map[int]bool inside graph[u] for constant time lookup). Sorting and binary search (Sort graph[u] slice and use binary search to find v) adds overhead.

2. Final Answer:

   Use a map[int]bool inside graph[u] for constant time lookup -> Option C

3. Quick Check:

   Map lookup faster than slice iteration [OK]

Hint: Use map for neighbors to check edges fast [OK]

Common Mistakes:

• Trying to index slice by node value directly
• Ignoring performance of linear search
• Overcomplicating with sorting when map is simpler