Adjacency Matrix Representation in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix after adding edges

What is the printed adjacency matrix after adding edges between nodes 0-1, 1-2, and 2-0 in an undirected graph with 3 nodes?

DSA Go

package main
import "fmt"
func main() {
  n := 3
  matrix := make([][]int, n)
  for i := range matrix {
    matrix[i] = make([]int, n)
  }
  matrix[0][1] = 1
  matrix[1][0] = 1
  matrix[1][2] = 1
  matrix[2][1] = 1
  matrix[2][0] = 1
  matrix[0][2] = 1
  for i := 0; i < n; i++ {
    fmt.Println(matrix[i])
  }
}

A

[0 1 1]
[1 0 1]
[1 1 0]

B

[1 1 1]
[1 1 1]
[1 1 1]

C

[0 0 0]
[0 0 0]
[0 0 0]

D

[0 1 0]
[1 0 1]
[0 1 0]

💡 Hint

Remember that for an undirected graph, the adjacency matrix is symmetric.

Edges between nodes 0-1, 1-2, and 2-0 mean matrix entries for both directions are set to 1, making the matrix symmetric with zeros on the diagonal.

❓ Predict Output

intermediate

Output of adjacency matrix for directed graph

What is the printed adjacency matrix after adding directed edges from node 0 to 1, and from node 1 to 2 in a graph with 3 nodes?

DSA Go

package main
import "fmt"
func main() {
  n := 3
  matrix := make([][]int, n)
  for i := range matrix {
    matrix[i] = make([]int, n)
  }
  matrix[0][1] = 1
  matrix[1][2] = 1
  for i := 0; i < n; i++ {
    fmt.Println(matrix[i])
  }
}

A

[1 0 0]
[0 1 0]
[0 0 1]

B

[0 1 1]
[1 0 1]
[1 1 0]

C

[0 1 0]
[0 0 1]
[0 0 0]

D

[0 0 0]
[0 0 0]
[0 0 0]

💡 Hint

Directed edges only set one direction in the matrix.

Only matrix[0][1] and matrix[1][2] are set to 1, others remain 0.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this Go code produce when initializing an adjacency matrix for 3 nodes? package main import "fmt" func main() { n := 3 matrix := make([]int, n) for i := 0; i < n; i++ { matrix[i] = make([]int, n) } fmt.Println(matrix) }

A prints [[0 0 0] [0 0 0] [0 0 0]]

B index out of range runtime error

C nil pointer dereference runtime error

D cannot assign []int to int (compile-time error)

💡 Hint

Check the type of 'matrix' and what make returns.

make([]int, n) creates a slice of ints, but matrix is declared as []int, so matrix[i] = make([]int, n) tries to assign a slice to an int element causing a compile-time error.

🧠 Conceptual

advanced

Memory usage of adjacency matrix vs adjacency list

For a graph with 1000 nodes and 10 edges, which statement about memory usage is true?

A Adjacency list uses more memory because it stores all edges explicitly

B Adjacency matrix uses more memory because it stores 1,000,000 entries regardless of edges

C Both use the same memory because they represent the same graph

D Adjacency matrix uses less memory because it uses a 2D array

💡 Hint

Think about how adjacency matrix size depends on number of nodes, not edges.

Adjacency matrix size is n*n (1,000,000 entries), while adjacency list stores only edges (10), so matrix uses more memory for sparse graphs.

🚀 Application

expert

Find if graph is complete using adjacency matrix

Given an undirected graph with n nodes represented by an adjacency matrix, which Go function correctly checks if the graph is complete (every pair of distinct nodes connected)?

A

func isComplete(matrix [][]int) bool {
  n := len(matrix)
  for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
      if i != j && matrix[i][j] == 0 {
        return false
      }
    }
  }
  return true
}

B

func isComplete(matrix [][]int) bool {
  n := len(matrix)
  for i := 0; i < n; i++ {
    if matrix[i][i] == 1 {
      return false
    }
  }
  return true
}

C

func isComplete(matrix [][]int) bool {
  n := len(matrix)
  for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
      if matrix[i][j] == 0 {
        return false
      }
    }
  }
  return true
}

D

func isComplete(matrix [][]int) bool {
  n := len(matrix)
  for i := 0; i < n; i++ {
    for j := i + 1; j < n; j++ {
      if matrix[i][j] == 0 {
        return false
      }
    }
  }
  return true
}

💡 Hint

Check all pairs except self loops must have edge 1.

Option A checks all pairs i != j for edge presence. Option A misses checking symmetric entries for undirected graph. Option A only checks diagonal. Option A incorrectly checks diagonal too.

Practice

1. What does an adjacency matrix represent in graph data structures?

easy

A. A 2D array showing connections between nodes

B. A list of nodes with their neighbors

C. A sequence of edges in order

D. A tree structure of nodes

Solution

1. Step 1: Understand adjacency matrix concept

   An adjacency matrix is a 2D array where rows and columns represent nodes.

2. Step 2: Identify what the matrix stores

   Each cell shows if there is a connection (edge) between two nodes.

3. Final Answer:

   A 2D array showing connections between nodes -> Option A

4. Quick Check:

   Adjacency matrix = 2D array [OK]

Hint: Adjacency matrix is always a 2D grid of node connections [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores edges as a list
• Assuming it represents a tree only

2. Which of the following is the correct way to declare a 3x3 adjacency matrix in Go?

easy

A. var matrix [3][3]int

B. matrix := make([]int, 3)

C. var matrix [][]int = make([][]int, 3)

D. matrix := [3]int{3}

Solution

1. Step 1: Understand Go array declaration

   In Go, a fixed-size 2D array is declared as [rows][cols]type.

2. Step 2: Check each option

   var matrix [3][3]int declares a 3x3 int array correctly. matrix := make([]int, 3) is a 1D slice. var matrix [][]int = make([][]int, 3) is a slice of slices but incomplete. matrix := [3]int{3} is a 1D array with wrong initialization.

3. Final Answer:

   var matrix [3][3]int -> Option A

4. Quick Check:

   Fixed 2D array = [3][3]int [OK]

Hint: Use [rows][cols]type for fixed 2D arrays in Go [OK]

Common Mistakes:

• Using slices instead of arrays for fixed size
• Incorrect initialization syntax
• Confusing 1D and 2D declarations

3. Given the following Go code, what is the printed adjacency matrix?

package main
import "fmt"
func main() {
  var graph [3][3]int
  graph[0][1] = 1
  graph[1][2] = 1
  graph[2][0] = 1
  for i := 0; i < 3; i++ {
    for j := 0; j < 3; j++ {
      fmt.Print(graph[i][j], " ")
    }
    fmt.Println()
  }
}

medium

A. 0 0 1
1 0 0
0 1 0

B. 1 0 0
0 1 0
0 0 1

C. 0 1 0
0 0 1
1 0 0

D. 0 1 1
1 0 1
1 1 0

Solution

1. Step 1: Trace assignments to the matrix

   graph[0][1] = 1 means node 0 connects to 1; graph[1][2] = 1 means node 1 connects to 2; graph[2][0] = 1 means node 2 connects to 0.

2. Step 2: Print matrix row by row

   Row 0: 0 1 0; Row 1: 0 0 1; Row 2: 1 0 0.

3. Final Answer:

   0 1 0 0 0 1 1 0 0 -> Option C

4. Quick Check:

   Edges set match matrix rows [OK]

Hint: Map edges to matrix cells row-wise [OK]

Common Mistakes:

• Mixing row and column indices
• Assuming symmetric matrix for directed graph
• Forgetting zero initialization

4. Identify the error in this Go code snippet for creating an adjacency matrix:

var graph [][]int
for i := 0; i < 3; i++ {
  graph[i] = make([]int, 3)
}

medium

A. graph should be a 1D slice

B. make([]int, 3) is incorrect syntax

C. Loop should run from 1 to 3

D. graph is not initialized before assignment

Solution

1. Step 1: Check graph slice initialization

   graph is declared but not initialized with length, so graph[i] access causes runtime error.

2. Step 2: Fix initialization

   graph should be initialized with length 3 before assigning inner slices, e.g., graph = make([][]int, 3).

3. Final Answer:

   graph is not initialized before assignment -> Option D

4. Quick Check:

   Initialize outer slice before indexing [OK]

Hint: Initialize slices before indexing to avoid runtime errors [OK]

Common Mistakes:

• Forgetting to initialize outer slice
• Confusing slice length and capacity
• Incorrect loop ranges

5. You have an undirected graph with 4 nodes. Which code snippet correctly updates the adjacency matrix to add an edge between node 1 and node 3?

hard

A. graph[1][3] = 1

B. graph[1][3] = 1; graph[3][1] = 1

C. graph[3][1] = 1

D. graph[1][1] = 1; graph[3][3] = 1

Solution

1. Step 1: Understand undirected graph edge representation

   In undirected graphs, edges are bidirectional, so adjacency matrix must be symmetric.

2. Step 2: Update both directions in matrix

   Set graph[1][3] = 1 and graph[3][1] = 1 to represent the edge correctly.

3. Final Answer:

   graph[1][3] = 1; graph[3][1] = 1 -> Option B

4. Quick Check:

   Undirected edge updates both matrix cells [OK]

Hint: Update both [i][j] and [j][i] for undirected edges [OK]

Common Mistakes:

• Updating only one direction for undirected graph
• Setting diagonal elements instead of edge cells
• Confusing node indices