Why Adjacency Matrix Representation in DSA C#?

The Big Idea

Discover how a simple grid can turn a messy list of connections into lightning-fast friendship checks!

The Scenario

Imagine you want to keep track of friendships in a group of people using a big table where each row and column represents a person. Without a clear system, you might write down each friendship on paper, making it hard to find if two people are friends quickly.

The Problem

Writing down each friendship manually is slow and confusing. Checking if two people are friends means scanning through a long list, which wastes time and can cause mistakes. As the group grows, this becomes impossible to manage easily.

The Solution

An adjacency matrix is like a neat grid where rows and columns represent people, and each cell tells if two people are friends. This makes checking friendships fast and simple, just by looking at one spot in the grid.

Before vs After

✗ Before

bool AreFriends(string personA, string personB, List<(string, string)> friendships) {
    foreach (var pair in friendships) {
        if ((pair.Item1 == personA && pair.Item2 == personB) || (pair.Item1 == personB && pair.Item2 == personA))
            return true;
    }
    return false;
}

✓ After

bool[,] adjacencyMatrix = new bool[numberOfPeople, numberOfPeople];

bool AreFriends(int indexA, int indexB) {
    return adjacencyMatrix[indexA, indexB];
}

What It Enables

This lets you quickly find connections between any two points in a network, making complex relationship checks simple and fast.

Real Life Example

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

Key Takeaways

Manual tracking of connections is slow and error-prone.

Adjacency matrix uses a grid to represent connections clearly.

It allows fast and easy checking of relationships.

Practice

1. What does an adjacency matrix represent in graph theory?

easy

A. A queue of nodes to visit

B. A list of nodes in the graph

C. A 2D array showing edges between nodes

D. A stack of visited 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 an edge exists between two nodes (1 for edge, 0 for no edge).

3. Final Answer:

   A 2D array showing edges between nodes -> Option C

4. Quick Check:

   Adjacency matrix = 2D array of edges [OK]

Hint: Adjacency matrix is always a 2D array showing connections [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of edges
• Mixing up matrix with traversal order

2. Which of the following is the correct way to declare an adjacency matrix for 4 nodes in C#?

easy

A. int[] matrix = new int[4];

B. int[,] matrix = new int[4,4];

C. int[][] matrix = new int[4];

D. int matrix = new int[4,4];

Solution

1. Step 1: Identify correct 2D array syntax in C#

   In C#, a 2D array is declared as int[,] with size [rows, columns].

2. Step 2: Check each option

   int[,] matrix = new int[4,4]; uses int[,] with size [4,4], correct for adjacency matrix of 4 nodes.

3. Final Answer:

   int[,] matrix = new int[4,4]; -> Option B

4. Quick Check:

   2D array syntax = int[,] [OK]

Hint: Use int[,] for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged array syntax instead of 2D array
• Declaring 1D array for adjacency matrix
• Missing comma in array declaration

3. Given the following adjacency matrix for a graph with 3 nodes:

int[,] matrix = new int[,] {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};

What is the output of Console.WriteLine(matrix[1,2]);?

medium

A. 1

B. 0

C. 2

D. Error

Solution

1. Step 1: Locate matrix element at row 1, column 2

   Matrix rows and columns start at 0, so matrix[1,2] is second row, third column.

2. Step 2: Check value at matrix[1,2]

   From the matrix, second row is {1, 0, 1}, third element is 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   matrix[1,2] = 1 [OK]

Hint: Remember zero-based indexing for matrix rows and columns [OK]

Common Mistakes:

• Confusing row and column indices
• Assuming 1-based indexing
• Misreading matrix values

4. Identify the error in this C# code snippet for creating an adjacency matrix of 3 nodes:

int[] matrix = new int[3];
matrix[0,1] = 1;

medium

A. Incorrect array declaration syntax

B. No error, code is correct

C. Index out of range error

D. Cannot assign value to matrix[0,1]

Solution

1. Step 1: Analyze array declaration

   int[] matrix = new int[3]; declares a 1D array of 3 integers.

2. Step 2: Examine the assignment

   matrix[0,1] = 1; attempts to use 2D indexing on a 1D array, which is invalid in C#.

3. Final Answer:

   Cannot assign value to matrix[0,1] -> Option D

4. Quick Check:

   1D array indexing mismatch [OK]

Hint: 1D arrays cannot use [row,col] indexing [OK]

Common Mistakes:

• Using 2D indexing on 1D array
• Assuming jagged array syntax for 2D array
• Ignoring compiler error messages

5. You have a directed graph with 4 nodes. Which adjacency matrix correctly represents edges from node 0 to 1 and 2, and from node 3 to 0?

hard

A. int[,] matrix = new int[,] {
{0, 1, 1, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{1, 0, 0, 0}
};

B. int[,] matrix = new int[,] {
{0, 1, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
{0, 0, 0, 1}
};

C. int[,] matrix = new int[,] {
{0, 0, 0, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{0, 1, 1, 0}
};

D. int[,] matrix = new int[,] {
{0, 1, 1, 0},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 0}
};

Solution

1. Step 1: Understand directed edges in adjacency matrix

   For directed graph, matrix[i,j] = 1 means edge from node i to node j.

2. Step 2: Check edges from node 0 to 1 and 2

   Row 0 should have 1s at columns 1 and 2.

3. Step 3: Check edge from node 3 to 0

   Row 3 should have 1 at column 0.

4. Step 4: Verify options

   int[,] matrix = new int[,] { {0, 1, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 0, 0} }; matches all conditions exactly.

5. Final Answer:

   {{0, 1, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 0, 0}} -> Option A

6. Quick Check:

   Directed edges = matrix[i,j] = 1 [OK]

Hint: Row = from node, column = to node in adjacency matrix [OK]

Common Mistakes:

• Confusing rows and columns for direction
• Using symmetric matrix for directed graph
• Missing edges or adding extra edges