Why Adjacency Matrix Representation in DSA Go?

The Big Idea

Discover how a simple table can turn a messy friendship list into a powerful connection map!

The Scenario

Imagine you want to keep track of friendships in a small group of people using just a paper and pencil. You try to write down who is friends with whom by listing every pair manually.

The Problem

This manual method quickly becomes confusing and slow as the group grows. You might forget some pairs or write duplicates. Checking if two people are friends means scanning through your messy notes.

The Solution

An adjacency matrix is like a neat table where rows and columns represent people, and each cell shows if a friendship exists. This makes checking and updating friendships fast and clear.

Before vs After

✗ Before

var friendships = map[string][]string{
  "Alice": {"Bob", "Carol"},
  "Bob": {"Alice"},
}
// To check if Alice and Bob are friends, scan Alice's list

✓ After

var adjacencyMatrix = [][]int{
  {0, 1, 1},
  {1, 0, 0},
  {1, 0, 0},
}
// Check if Alice and Bob are friends by adjacencyMatrix[0][1] == 1

What It Enables

It enables quick and simple checks of connections between any two points in a network.

Real Life Example

Social media platforms use adjacency matrices to quickly find if two users are connected or to suggest new friends.

Key Takeaways

Manual tracking of connections is slow and error-prone.

Adjacency matrix uses a clear table to represent connections.

This method makes checking and updating connections fast and easy.

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