Adjacency List Representation in DSA Go - Build from Scratch

Adjacency List Representation

📖 Scenario: You are helping a city planner represent the roads connecting different neighborhoods. Each neighborhood is a node, and roads are connections between them. You will create a simple map using an adjacency list to show which neighborhoods connect directly.

🎯 Goal: Build an adjacency list representation of a graph using a Go map where keys are neighborhood names and values are slices of connected neighborhoods.

📋 What You'll Learn

Create a map called graph with string keys and slice of strings as values

Add a variable called startNeighborhood with the value "Downtown"

Use a for loop with variables neighbor to iterate over graph[startNeighborhood]

Print each neighbor inside the loop

💡 Why This Matters

🌍 Real World

Adjacency lists are used to represent networks like roads, social connections, or computer networks efficiently.

💼 Career

Understanding adjacency lists is essential for software engineers working with graph algorithms, network analysis, and data modeling.

1

Create the adjacency list map

Create a map called graph with string keys and slice of strings as values. Add these exact entries: "Downtown": {"Uptown", "Midtown"}, "Uptown": {"Downtown", "Suburb"}, "Midtown": {"Downtown"}, "Suburb": {"Uptown"}.

DSA Go

// Create the graph map with neighborhoods and their connections
// Your code here

Hint

Use map[string][]string to create the adjacency list. Each key is a neighborhood name, and the value is a slice of connected neighborhoods.

2

Add a start neighborhood variable

Add a variable called startNeighborhood and set it to the string "Downtown".

DSA Go

package main

import "fmt"

func main() {
    graph := map[string][]string{
        "Downtown": {"Uptown", "Midtown"},
        "Uptown": {"Downtown", "Suburb"},
        "Midtown": {"Downtown"},
        "Suburb": {"Uptown"},
    }
    // Add startNeighborhood variable here
    // Your code here
}

Hint

Use startNeighborhood := "Downtown" to create the variable.

3

Loop through neighbors of the start neighborhood

Use a for loop with variable neighbor to iterate over graph[startNeighborhood].

DSA Go

package main

import "fmt"

func main() {
    graph := map[string][]string{
        "Downtown": {"Uptown", "Midtown"},
        "Uptown": {"Downtown", "Suburb"},
        "Midtown": {"Downtown"},
        "Suburb": {"Uptown"},
    }
    startNeighborhood := "Downtown"
    // Loop through neighbors of startNeighborhood
    // Your code here
}

Hint

Use for _, neighbor := range graph[startNeighborhood] to loop through neighbors.

4

Print each neighbor

Inside the for loop, print each neighbor using fmt.Println(neighbor).

DSA Go

package main

import "fmt"

func main() {
    graph := map[string][]string{
        "Downtown": {"Uptown", "Midtown"},
        "Uptown": {"Downtown", "Suburb"},
        "Midtown": {"Downtown"},
        "Suburb": {"Uptown"},
    }
    startNeighborhood := "Downtown"
    for _, neighbor := range graph[startNeighborhood] {
        // Print neighbor here
        // Your code here
    }
}

Hint

Use fmt.Println(neighbor) inside the loop to print each connected neighborhood.

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