Adjacency Matrix Representation in DSA C#

Mental Model

We use a square grid to show which points (nodes) connect to which others. Each cell says yes or no if two points link.

Analogy: Imagine a city map with intersections as points and roads as connections. The grid is like a table where each row and column is an intersection, and a mark means a road connects them.

   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: Show which nodes connect using a matrix

Step 1: Start with a 3x3 matrix filled with zeros

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

Why: We need a blank grid to mark connections

Step 2: Mark connection from node 0 to node 1

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

Why: Node 0 connects to node 1, so mark that spot

Step 3: Mark connection from node 1 to node 0 (undirected graph)

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

Why: Since connection is two-way, mark the reverse too

Step 4: Mark connection from node 1 to node 2

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

Why: Node 1 connects to node 2, mark it

Step 5: Mark connection from node 2 to node 1 (undirected graph)

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

Why: Mark reverse connection for two-way link

Result:

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

Annotated Code

DSA C#

using System;

class Graph
{
    private int[,] matrix;
    private int size;

    public Graph(int nodes)
    {
        size = nodes;
        matrix = new int[size, size];
    }

    public void AddEdge(int from, int to)
    {
        matrix[from, to] = 1; // mark connection from 'from' to 'to'
        matrix[to, from] = 1; // mark reverse connection for undirected graph
    }

    public void PrintMatrix()
    {
        Console.Write("   ");
        for (int i = 0; i < size; i++)
            Console.Write(i + " ");
        Console.WriteLine();

        for (int i = 0; i < size; i++)
        {
            Console.Write(i + " [");
            for (int j = 0; j < size; j++)
            {
                Console.Write(matrix[i, j]);
                if (j != size - 1) Console.Write(" ");
            }
            Console.WriteLine("]");
        }
    }
}

class Program
{
    static void Main()
    {
        Graph g = new Graph(3);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.PrintMatrix();
    }
}

matrix[from, to] = 1; // mark connection from 'from' to 'to'

mark connection in matrix for edge start to end

matrix[to, from] = 1; // mark reverse connection for undirected graph

mark reverse connection for undirected graph

for (int i = 0; i < size; i++)

iterate rows to print matrix

for (int j = 0; j < size; j++)

iterate columns to print matrix

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 a matrix of size n by n

Space: O(n^2) because the matrix stores connection info for every pair of nodes

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

Edge Cases

Graph with zero nodes

Matrix is empty, no edges to add or print

DSA C#

size = nodes;

Graph with one node and no edges

Matrix is 1x1 with zero, no connections

DSA C#

matrix = new int[size, size];

Adding edge with invalid node index

Code may throw error or ignore, no explicit guard in code

DSA C#

None (no explicit check)

When to Use This Pattern

When you need to quickly check if two nodes connect and the graph is small or dense, use adjacency matrix because it gives instant yes/no answers.

Common Mistakes

Mistake: Forgetting to mark the reverse connection in undirected graphs
Fix: Always mark both matrix[from, to] and matrix[to, from] for undirected edges

Mistake: Using adjacency matrix for very large sparse graphs causing high memory use
Fix: Use adjacency list instead for large sparse graphs

Summary

It shows graph connections in a square grid where each cell says if two nodes connect.

Use it when you want fast checks for edges and the graph is not too big.

The key is that each row and column represent nodes, and a 1 means a connection.

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