Adjacency List vs Matrix When to Choose Which in DSA Go - Build Both Approaches

Adjacency List vs Matrix When to Choose Which

📖 Scenario: You are working on a simple social network app where users can be friends with each other. You want to represent the friendship connections between users using graphs.There are two common ways to represent graphs: adjacency lists and adjacency matrices. Each has its own advantages depending on the number of users and connections.

🎯 Goal: Build two graph representations for the same set of users and friendships: one using an adjacency list and one using an adjacency matrix. Then, print both to see how they look.This will help you understand when to choose adjacency lists or matrices.

📋 What You'll Learn

Create an adjacency list for 4 users with given friendships

Create an adjacency matrix for the same users and friendships

Use clear variable names: adjList and adjMatrix

Print both data structures to compare their formats

💡 Why This Matters

🌍 Real World

Social networks, recommendation systems, and many other applications use graphs to represent connections between entities.

💼 Career

Understanding graph representations is essential for software engineers working on network analysis, pathfinding algorithms, and data modeling.

1

Create the adjacency list

Create a variable called adjList of type map[int][]int representing the friendships between 4 users. Use these exact connections: user 0 is friends with 1 and 2, user 1 is friends with 0 and 3, user 2 is friends with 0, and user 3 is friends with 1.

DSA Go

# Your code here

Hint

Use a map where keys are user IDs and values are slices of friend user IDs.

2

Create the adjacency matrix

Add a variable called adjMatrix of type [4][4]int representing the same friendships. Set adjMatrix[i][j] = 1 if user i is friends with user j, otherwise 0. Use the exact connections from Step 1.

DSA Go

package main

import "fmt"

func main() {
    adjList := map[int][]int{
        0: {1, 2},
        1: {0, 3},
        2: {0},
        3: {1},
    }

    // Your code here
}

Hint

Use a 4x4 array of integers and set 1 where friendships exist.

3

Print the adjacency list

Use a for loop with variables user and friends to iterate over adjList. Inside the loop, print the user and their friends in this format: User X: [list of friends].

DSA Go

package main

import "fmt"

func main() {
    adjList := map[int][]int{
        0: {1, 2},
        1: {0, 3},
        2: {0},
        3: {1},
    }

    var adjMatrix [4][4]int
    adjMatrix[0][1] = 1
    adjMatrix[0][2] = 1
    adjMatrix[1][0] = 1
    adjMatrix[1][3] = 1
    adjMatrix[2][0] = 1
    adjMatrix[3][1] = 1

    // Your code here
}

Hint

Use range to loop over the map and fmt.Printf to print formatted output.

4

Print the adjacency matrix

Use two nested for loops with variables i and j to iterate over adjMatrix. Print each row on a new line with values separated by spaces. Use fmt.Println() and fmt.Print() to format the output exactly.

DSA Go

package main

import "fmt"

func main() {
    adjList := map[int][]int{
        0: {1, 2},
        1: {0, 3},
        2: {0},
        3: {1},
    }

    var adjMatrix [4][4]int
    adjMatrix[0][1] = 1
    adjMatrix[0][2] = 1
    adjMatrix[1][0] = 1
    adjMatrix[1][3] = 1
    adjMatrix[2][0] = 1
    adjMatrix[3][1] = 1

    for user, friends := range adjList {
        fmt.Printf("User %d: %v\n", user, friends)
    }

    // Your code here
}

Hint

Use nested loops to print each row of the matrix with spaces, then a newline.

Practice

1. Which data structure is generally better for representing a graph with very few edges compared to the number of nodes?

easy

A. Adjacency List

B. Adjacency Matrix

C. Edge List

D. Incidence Matrix

Solution

1. Step 1: Understand graph density

   A graph with very few edges compared to nodes is called a sparse graph.

2. Step 2: Choose data structure for sparse graphs

   Adjacency lists store only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graph? Use adjacency list for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing edge list with adjacency matrix
• Assuming adjacency matrix is always better

2. Which of the following is the correct way to declare an adjacency matrix for a graph with 4 nodes in Go?

easy

A. var graph [4][4]int

B. graph := make([][]int, 4)

C. var graph []int

D. graph := map[int][]int{}

Solution

1. Step 1: Understand adjacency matrix declaration

   An adjacency matrix is a 2D fixed-size array representing edges between nodes.

2. Step 2: Check Go syntax for fixed 2D array

   "var graph [4][4]int" declares a 4x4 integer matrix correctly.

3. Final Answer:

   var graph [4][4]int -> Option A

4. Quick Check:

   Fixed 2D array = var graph [4][4]int [OK]

Hint: Adjacency matrix = fixed 2D array declaration [OK]

Common Mistakes:

• Using slice of slices without initialization for matrix
• Declaring 1D slice instead of 2D array
• Using map which is adjacency list style

3. Given the following Go code using an adjacency list, what will be printed?

graph := map[int][]int{
  0: {1, 2},
  1: {2},
  2: {0},
  3: {},
}
fmt.Println(graph[1])

medium

A. [0 2]

B. [2]

C. [1 2]

D. []

Solution

1. Step 1: Identify adjacency list entries for node 1

   Node 1 has edges to node 2 only, so graph[1] = {2}.

2. Step 2: Understand fmt.Println output

   Printing graph[1] outputs the slice [2].

3. Final Answer:

   [2] -> Option B

4. Quick Check:

   graph[1] = [2] [OK]

Hint: Print adjacency list for node key directly [OK]

Common Mistakes:

• Confusing keys and values in map
• Assuming node 1 connects to node 0
• Expecting adjacency matrix output

4. The following Go code attempts to create an adjacency matrix but has a bug. What is the bug?

graph := make([][]int, 3)
for i := range graph {
  graph[i] = make([]int, 3)
}
graph[0][1] = 1
graph[1][2] = 1
fmt.Println(graph[0][2])

medium

A. The matrix is not initialized properly

B. graph[0][2] should be 1 but prints 0

C. Index out of range error

D. No bug, code runs correctly

Solution

1. Step 1: Check matrix initialization

   Each row is initialized with make([]int, 3), so matrix is properly created.

2. Step 2: Check assigned values and print

   graph[0][1] and graph[1][2] are set to 1; graph[0][2] was never set, so prints 0.

3. Step 3: Verify no runtime errors

   All indices are within range; no errors occur.

4. Final Answer:

   No bug, code runs correctly -> Option D

5. Quick Check:

   Proper initialization and indexing = No bug [OK]

Hint: Check initialization and index ranges carefully [OK]

Common Mistakes:

• Assuming unassigned entries print 1
• Thinking initialization is missing
• Expecting index errors without out-of-range access

5. You need to represent a dense graph with 1000 nodes where you frequently check if an edge exists between any two nodes. Which data structure is best and why? A) Adjacency Matrix for constant-time edge checks B) Adjacency List for memory efficiency C) Edge List for simple iteration D) Map of maps for flexible keys

hard

A. Edge List for simple iteration

B. Adjacency List for memory efficiency

C. Adjacency Matrix for constant-time edge checks

D. Map of maps for flexible keys

Solution

1. Step 1: Understand graph density and operations

   A dense graph has many edges, close to the maximum possible.

2. Step 2: Choose data structure for fast edge existence checks

   Adjacency matrix allows O(1) time to check if edge exists between any two nodes.

3. Step 3: Consider memory tradeoff

   Though adjacency matrix uses more memory, for dense graphs this is acceptable and beneficial.

4. Final Answer:

   Adjacency Matrix for constant-time edge checks -> Option C

5. Quick Check:

   Dense graph + fast edge check = Adjacency Matrix [OK]

Hint: Dense graph + frequent edge checks? Use adjacency matrix [OK]

Common Mistakes:

• Choosing adjacency list for dense graphs slows edge checks
• Ignoring memory vs speed tradeoff
• Confusing edge list with adjacency matrix