Adjacency List vs Matrix When to Choose Which in DSA Go - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Prefer Adjacency List Over Matrix?

Which scenario is best suited for using an adjacency list instead of an adjacency matrix?

A A graph represented as a complete graph where every node connects to every other node.

B A graph with a small number of nodes and many edges (dense graph).

C A graph with many nodes but very few edges (sparse graph).

D A graph where you need to quickly check if an edge exists between any two nodes.

💡 Hint

Think about memory usage and efficiency when edges are few.

An adjacency list is efficient for sparse graphs because it stores only existing edges, saving memory and speeding up iteration over neighbors.

🧠 Conceptual

intermediate

When to Prefer Adjacency Matrix Over List?

In which case is an adjacency matrix a better choice than an adjacency list?

A When you need to quickly check if an edge exists between any two nodes.

B When the graph is very large and sparse.

C When you want to save memory for graphs with few edges.

D When you only need to iterate over neighbors of a node.

💡 Hint

Think about constant-time edge lookup.

An adjacency matrix allows O(1) time to check if an edge exists between any two nodes, which is useful for dense graphs or frequent edge queries.

❓ Predict Output

advanced

Output of Graph Representation Conversion

What is the output of the following Go code that converts an adjacency matrix to an adjacency list?

DSA Go

package main
import "fmt"
func main() {
  matrix := [][]int{
    {0,1,0},
    {1,0,1},
    {0,1,0},
  }
  adjList := make([][]int, len(matrix))
  for i := range matrix {
    for j, val := range matrix[i] {
      if val == 1 {
        adjList[i] = append(adjList[i], j)
      }
    }
  }
  fmt.Println(adjList)
}

A [[1] [0 2] [1]]

B [[1 2] [0 2] [1]]

C [[0 1] [1 2] [0 1]]

D [[1] [2] [0]]

💡 Hint

Check which nodes have edges (value 1) in the matrix rows.

The code appends indices of columns with value 1 for each row, creating adjacency lists: node 0 connects to 1, node 1 connects to 0 and 2, node 2 connects to 1.

🔧 Debug

advanced

Find the Bug in Adjacency Matrix Edge Check

What error will this Go code produce when checking if an edge exists between nodes 1 and 3 in a graph with 3 nodes?

DSA Go

package main
import "fmt"
func main() {
  matrix := [][]int{
    {0,1,0},
    {1,0,1},
    {0,1,0},
  }
  fmt.Println(matrix[1][3] == 1)
}

A compilation error

B false

C true

D runtime error: index out of range

💡 Hint

Check the size of the matrix and valid indices.

Accessing matrix[1][3] is invalid because the inner slice has length 3 with indices 0,1,2 only, causing an index out of range runtime error.

🚀 Application

expert

Choosing Graph Representation for a Social Network

You are designing a social network with millions of users but each user connects to only a few others. Which graph representation is best and why?

A Use adjacency matrix because it is simpler to implement for large graphs.

B Use adjacency list because it saves memory by storing only existing connections.

C Use adjacency matrix because it allows quick edge checks between any two users.

D Use adjacency list because it allows constant-time edge existence checks.

💡 Hint

Consider the number of edges per user and memory efficiency.

In a large sparse graph like a social network, adjacency lists save memory by storing only actual connections. Adjacency matrices waste memory and are inefficient.

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