Adjacency Matrix Representation in DSA Go - Execution Trace

Concept Flow - Adjacency Matrix Representation

Start

↓

Create NxN matrix

↓

Initialize all cells to 0

↓

For each edge (u,v)

↓

Set matrix[u

↓

If undirected, set matrix[v

↓

Repeat for all edges

↓

Adjacency matrix ready

Build a square matrix for all nodes, mark 1 where edges exist, 0 otherwise.

Execution Sample

DSA Go

nodes := 4
matrix := make([][]int, nodes)
for i := range matrix {
  matrix[i] = make([]int, nodes)
}
matrix[0][1] = 1
matrix[1][2] = 1
matrix[2][3] = 1

Create 4x4 matrix and mark edges 0->1, 1->2, 2->3.

Execution Table

Step	Operation	Matrix State	Pointer Changes	Visual State
1	Create 4x4 matrix	[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]	matrix initialized	4 rows and 4 columns, all zeros
2	Add edge 0->1	[[0 1 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]	matrix[0][1] = 1	Edge from node 0 to 1 marked
3	Add edge 1->2	[[0 1 0 0] [0 0 1 0] [0 0 0 0] [0 0 0 0]]	matrix[1][2] = 1	Edge from node 1 to 2 marked
4	Add edge 2->3	[[0 1 0 0] [0 0 1 0] [0 0 0 1] [0 0 0 0]]	matrix[2][3] = 1	Edge from node 2 to 3 marked
5	No more edges	[[0 1 0 0] [0 0 1 0] [0 0 0 1] [0 0 0 0]]	No pointer changes	Final adjacency matrix

💡 All edges processed, matrix fully represents graph

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
matrix	nil	[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]	[[0 1 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]	[[0 1 0 0] [0 0 1 0] [0 0 0 0] [0 0 0 0]]	[[0 1 0 0] [0 0 1 0] [0 0 0 1] [0 0 0 0]]	[[0 1 0 0] [0 0 1 0] [0 0 0 1] [0 0 0 0]]

Key Moments - 3 Insights

Why do we initialize the matrix with zeros before adding edges?

Because zeros mean no connection between nodes. See step 1 in execution_table where matrix is all zeros before edges are added.

Why do we set matrix[u][v] = 1 for each edge?

Setting 1 marks that there is a direct edge from node u to node v. Look at steps 2-4 in execution_table where each edge updates the matrix.

What if the graph is undirected? How does the matrix change?

For undirected graphs, we set both matrix[u][v] and matrix[v][u] to 1 for each edge. This is not shown here but would double mark edges symmetrically.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of matrix[1][2]?

A 0

B 1

C 2

D Undefined

💡 Hint

Check the 'Matrix State' column at step 3 in execution_table.

At which step does the edge from node 2 to node 3 get added?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' column in execution_table for when matrix[2][3] changes.

If the graph was undirected, what additional change would happen after step 2?

A matrix[2][1] would be set to 1

B matrix[0][2] would be set to 1

C matrix[1][0] would be set to 1

D No change needed

💡 Hint

For undirected graphs, edges are symmetric, so matrix[v][u] = 1 if matrix[u][v] = 1.

Concept Snapshot

Adjacency Matrix Representation:
- Use NxN matrix for N nodes
- Initialize all cells to 0 (no edges)
- For each edge u->v, set matrix[u][v] = 1
- For undirected graphs, also set matrix[v][u] = 1
- Matrix shows direct connections between nodes

Full Transcript

We start by creating a square matrix sized by the number of nodes. Initially, all cells are zero, meaning no connections. Then for each edge, we mark the matrix cell at row u and column v as 1 to show a direct edge from node u to node v. If the graph is undirected, we mark both matrix[u][v] and matrix[v][u] as 1. This matrix fully represents the graph's connections.

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