Adjacency Matrix Representation in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array used to represent a graph where each cell at row i and column j indicates if there is an edge from vertex i to vertex j.

beginner

How do you represent no edge between two vertices in an adjacency matrix?

You represent no edge by placing a 0 in the cell corresponding to those vertices in the adjacency matrix.

beginner

What is the size of an adjacency matrix for a graph with n vertices?

The adjacency matrix size is n x n, where n is the number of vertices in the graph.

intermediate

How does an adjacency matrix represent a weighted graph?

In a weighted graph, the adjacency matrix stores the weight of the edge between vertices instead of just 1 or 0. A 0 or special value indicates no edge.

intermediate

What is a disadvantage of using an adjacency matrix for sparse graphs?

An adjacency matrix uses O(n²) space, which can be inefficient for sparse graphs with few edges compared to other representations like adjacency lists.

What value is stored in an adjacency matrix cell if there is an edge between vertex 2 and vertex 3 in an unweighted graph?

A 1

B 0

C -1

D The weight of the edge

In an unweighted graph, an edge is represented by 1 in the adjacency matrix.

What is the time complexity to check if an edge exists between two vertices using an adjacency matrix?

A O(1)

B O(n)

C O(log n)

D O(n²)

Checking an edge in an adjacency matrix is direct access, so it takes constant time O(1).

Which graph type is adjacency matrix less efficient for?

A Dense graphs

B Complete graphs

C Sparse graphs

D Weighted graphs

Adjacency matrix uses a lot of space for sparse graphs where many edges are missing.

In a directed graph, what does the cell at row i and column j represent in the adjacency matrix?

A Edge from vertex j to vertex i

B Edge between vertex i and vertex j (undirected)

C No edge

D Edge from vertex i to vertex j

In directed graphs, the cell [i][j] shows if there is an edge from vertex i to vertex j.

How is a self-loop represented in an adjacency matrix?

A By a 0 in the diagonal cell [i][i]

B By a 1 in the diagonal cell [i][i]

C By a 1 in any off-diagonal cell

D Self-loops cannot be represented

A self-loop is an edge from a vertex to itself, shown by 1 in the diagonal cell.

Explain how an adjacency matrix represents edges in a graph and how it differs for directed and undirected graphs.

Think about how rows and columns relate to vertices and edge direction.

Describe the advantages and disadvantages of using an adjacency matrix compared to adjacency lists.

Consider time and space trade-offs.

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