Adjacency List Representation in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list is a way to represent a graph where each node stores a list of its neighbors. It shows which nodes are directly connected to it.

intermediate

How does adjacency list save space compared to adjacency matrix?

Adjacency list only stores edges that exist, so it uses less space for sparse graphs. Adjacency matrix stores all possible edges, using more space.

beginner

In Go, what data structure is commonly used to implement adjacency lists?

A map with keys as nodes and values as slices (lists) of neighbors is commonly used to implement adjacency lists in Go.

intermediate

What is the time complexity to find all neighbors of a node using adjacency list?

It is O(k), where k is the number of neighbors of that node, because adjacency list stores only neighbors directly.

beginner

Show the adjacency list representation of a graph with edges: 1-2, 1-3, 2-4.

1 -> [2, 3]
2 -> [1, 4]
3 -> [1]
4 -> [2]

Which data structure best represents an adjacency list in Go?

A map[int][]int

B [][]int

C map[int]int

D []int

A map with integer keys and slices of integers as values stores each node and its neighbors.

What is the main advantage of adjacency list over adjacency matrix?

A Uses less space for sparse graphs

B Faster to check if edge exists

C Always uses fixed space

D Simpler to implement

Adjacency list stores only existing edges, saving space when graph has few edges.

In adjacency list, how do you find neighbors of a node?

A Scan entire graph

B Look up the node's list in the map

C Check matrix row

D Neighbors are not stored

Neighbors are stored directly in the list for each node.

If a graph has 5 nodes and 4 edges, which representation is more space efficient?

A Adjacency matrix

B Both equal

C Adjacency list

D Depends on node values

Adjacency list uses space proportional to edges, better for few edges.

What is the output adjacency list for edges: 1-2, 2-3 in an undirected graph?

A 1 -> [], 2 -> [], 3 -> []

B 1 -> [2], 2 -> [3], 3 -> []

C 1 -> [1, 2], 2 -> [2, 3], 3 -> [3]

D 1 -> [2], 2 -> [1, 3], 3 -> [2]

Edges are bidirectional, so neighbors are listed both ways.

Explain how an adjacency list represents a graph and why it is useful.

Think about how you would list friends for each person.

Describe how you would implement an adjacency list in Go for an undirected graph.

Use Go's map and slices to store neighbors.

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