Adjacency List Representation in DSA Go

Mental Model

We store each node's neighbors in a list so we can quickly see who it connects to.

Analogy: Imagine a group of friends where each person keeps a list of their close friends. To find who someone knows, you just look at their list.

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

Dry Run Walkthrough

Input: Graph with edges: 0->1, 0->2, 1->2, 2->0, 2->3

Goal: Build adjacency lists showing neighbors for each node

Step 1: Add edge 0->1 by appending 1 to list of 0

0 -> [1]
1 -> []
2 -> []
3 -> []

Why: We record that node 0 connects to node 1

Step 2: Add edge 0->2 by appending 2 to list of 0

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

Why: We record that node 0 also connects to node 2

Step 3: Add edge 1->2 by appending 2 to list of 1

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

Why: We record that node 1 connects to node 2

Step 4: Add edge 2->0 by appending 0 to list of 2

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

Why: We record that node 2 connects back to node 0

Step 5: Add edge 2->3 by appending 3 to list of 2

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

Why: We record that node 2 connects to node 3

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

// Graph represents a directed graph using adjacency list
type Graph struct {
	adjacencyList map[int][]int
}

// NewGraph creates a new graph with given number of nodes
func NewGraph() *Graph {
	return &Graph{adjacencyList: make(map[int][]int)}
}

// AddEdge adds a directed edge from src to dest
func (g *Graph) AddEdge(src, dest int) {
	g.adjacencyList[src] = append(g.adjacencyList[src], dest) // add dest to src's list
}

// PrintGraph prints the adjacency list of the graph
func (g *Graph) PrintGraph() {
	for node := 0; node < 4; node++ {
		neighbors := g.adjacencyList[node]
		fmt.Printf("%d -> %v\n", node, neighbors) // show neighbors
	}
}

func main() {
	g := NewGraph()
	g.AddEdge(0, 1) // add edge 0->1
	g.AddEdge(0, 2) // add edge 0->2
	g.AddEdge(1, 2) // add edge 1->2
	g.AddEdge(2, 0) // add edge 2->0
	g.AddEdge(2, 3) // add edge 2->3
	g.PrintGraph() // print adjacency list
}

g.adjacencyList[src] = append(g.adjacencyList[src], dest) // add dest to src's list

append destination node to source node's adjacency list to record edge

for node := 0; node < 4; node++ {

iterate over all nodes to print their neighbors

fmt.Printf("%d -> %v\n", node, neighbors) // show neighbors

display adjacency list for each node

Output

0 -> [1 2]

1 -> [2]

2 -> [0 3]

3 -> []

Complexity Analysis

Time: O(V + E) because we add each edge once and print each node's neighbors once

Space: O(V + E) because we store a list of neighbors for each node and each edge

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more efficient for sparse graphs

Edge Cases

Node with no outgoing edges

Its adjacency list is empty, showing no neighbors

DSA Go

neighbors := g.adjacencyList[node]

Graph with no edges

All adjacency lists are empty

DSA Go

neighbors := g.adjacencyList[node]

Adding edge from node not yet in map

Map creates new entry with appended neighbor

DSA Go

g.adjacencyList[src] = append(g.adjacencyList[src], dest)

When to Use This Pattern

When you need to represent a graph efficiently and quickly find neighbors of nodes, use adjacency list representation because it stores only existing edges.

Common Mistakes

Mistake: Using a fixed-size array for adjacency lists causing index errors
Fix: Use a map or dynamic slices to handle nodes flexibly

Mistake: Appending edges to wrong node's list
Fix: Always append destination to source node's adjacency list

Summary

Stores each node's neighbors in a list for efficient graph representation.

Use when you want to save space and quickly access neighbors in sparse graphs.

The key is to keep a list of connected nodes for each node instead of a big matrix.

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