Adjacency Matrix Representation in DSA Go

Mental Model

An adjacency matrix is a grid that shows which nodes in a graph connect to which others using rows and columns.

Analogy: Think of a classroom seating chart where each student is listed in rows and columns, and a mark shows if two students are friends sitting next to each other.

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

Dry Run Walkthrough

Input: Graph with 3 nodes: edges between 0-1 and 1-2

Goal: Create an adjacency matrix showing connections between nodes

Step 1: Initialize a 3x3 matrix filled with zeros

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

Why: Start with no connections marked

Step 2: Mark connection between node 0 and node 1

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

Why: Graph is undirected, so mark both [0][1] and [1][0]

Step 3: Mark connection between node 1 and node 2

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

Why: Mark both [1][2] and [2][1] for undirected edge

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

// Graph holds adjacency matrix and number of nodes
type Graph struct {
	adjMatrix [][]int
	nodes     int
}

// NewGraph creates a graph with n nodes and empty adjacency matrix
func NewGraph(n int) *Graph {
	matrix := make([][]int, n)
	for i := 0; i < n; i++ {
		matrix[i] = make([]int, n) // initialize row with zeros
	}
	return &Graph{adjMatrix: matrix, nodes: n}
}

// AddEdge adds an undirected edge between src and dest
func (g *Graph) AddEdge(src, dest int) {
	// mark both directions for undirected graph
	g.adjMatrix[src][dest] = 1
	g.adjMatrix[dest][src] = 1
}

// PrintMatrix prints the adjacency matrix
func (g *Graph) PrintMatrix() {
	fmt.Print("   ")
	for i := 0; i < g.nodes; i++ {
		fmt.Printf("%d ", i)
	}
	fmt.Println()
	for i := 0; i < g.nodes; i++ {
		fmt.Printf("%d ", i)
		fmt.Print("[")
		for j := 0; j < g.nodes; j++ {
			fmt.Printf("%d", g.adjMatrix[i][j])
			if j != g.nodes-1 {
				fmt.Print(" ")
			}
		}
		fmt.Println("]")
	}
}

func main() {
	// Create graph with 3 nodes
	graph := NewGraph(3)
	// Add edges 0-1 and 1-2
	graph.AddEdge(0, 1)
	graph.AddEdge(1, 2)
	// Print adjacency matrix
	graph.PrintMatrix()
}

matrix := make([][]int, n) for i := 0; i < n; i++ { matrix[i] = make([]int, n) // initialize row with zeros }

initialize n x n matrix with zeros to represent no edges

g.adjMatrix[src][dest] = 1 g.adjMatrix[dest][src] = 1

mark edges in both directions for undirected graph

for i := 0; i < g.nodes; i++ { for j := 0; j < g.nodes; j++ { fmt.Printf("%d", g.adjMatrix[i][j]) if j != g.nodes-1 { fmt.Print(" ") } } }

print the adjacency matrix row by row

Output

   0 1 2

0 [0 1 0]

1 [1 0 1]

2 [0 1 0]

Complexity Analysis

Time: O(n^2) because we create and print an n by n matrix

Space: O(n^2) because the adjacency matrix stores n squared elements

vs Alternative: Compared to adjacency lists which use O(n + e) space, adjacency matrix uses more space but allows O(1) edge checks

Edge Cases

Graph with zero nodes

Creates empty matrix and prints nothing

DSA Go

matrix := make([][]int, n)

Graph with one node and no edges

Matrix is 1x1 with zero, no edges

DSA Go

matrix[i] = make([]int, n)

Adding edge with invalid node index

Program may panic or error (not handled in code)

DSA Go

No explicit guard; user must provide valid indices

When to Use This Pattern

When you need to quickly check if two nodes are connected and the graph is small or dense, use adjacency matrix because it gives instant edge lookup.

Common Mistakes

Mistake: Marking only one direction in an undirected graph
Fix: Always mark both [src][dest] and [dest][src] to keep symmetry

Mistake: Not initializing the matrix rows properly leading to nil slices
Fix: Initialize each row slice separately inside a loop

Summary

It stores graph connections in a 2D grid where rows and columns represent nodes.

Use it when the graph is small or dense and you want fast edge checks.

The key is that each cell shows if two nodes connect, making lookups instant but using more space.

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