Adjacency Matrix Representation in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency matrix after adding edges

What is the printed adjacency matrix after adding edges between nodes 0-1, 1-2, and 2-0 in an undirected graph with 3 nodes?

DSA C#

int n = 3;
int[,] matrix = new int[n, n];
matrix[0, 1] = 1;
matrix[1, 0] = 1;
matrix[1, 2] = 1;
matrix[2, 1] = 1;
matrix[2, 0] = 1;
matrix[0, 2] = 1;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        Console.Write(matrix[i, j] + " ");
    }
    Console.WriteLine();
}

A [[1,1,1],[1,1,1],[1,1,1]]

B [[0,1,0],[1,0,1],[0,1,0]]

C [[0,0,1],[0,0,1],[1,1,0]]

D [[0,1,1],[1,0,1],[1,1,0]]

💡 Hint

Remember that for an undirected graph, the adjacency matrix is symmetric.

Edges 0-1, 1-2, and 2-0 are added symmetrically, so matrix[i,j] and matrix[j,i] are set to 1 for these pairs. The diagonal remains 0 because no self-loops are added.

❓ Predict Output

intermediate

Value in adjacency matrix after removing an edge

Given a directed graph with 3 nodes and edges 0->1, 1->2, 2->0, what is the value of matrix[1,2] after removing the edge 1->2?

DSA C#

int n = 3;
int[,] matrix = new int[n, n];
matrix[0, 1] = 1;
matrix[1, 2] = 1;
matrix[2, 0] = 1;
matrix[1, 2] = 0; // remove edge
Console.WriteLine(matrix[1, 2]);

A 0

B 1

C null

D -1

💡 Hint

Removing an edge sets the corresponding matrix cell to 0.

The edge 1->2 is removed by setting matrix[1,2] to 0, so printing matrix[1,2] outputs 0.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this C# code produce when trying to create an adjacency matrix for 3 nodes? int[,] matrix = new int[3];

DSA C#

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

A CS0029: Cannot implicitly convert type 'int[]' to 'int[,]'

B CS0308: The non-generic type 'System.Int32' cannot be used with type arguments

C CS1660: Cannot convert lambda expression to type 'int' because it is not a delegate type

D CS1501: No overload for method 'int' takes 1 arguments

💡 Hint

Check the syntax for declaring a 2D array in C#.

The code declares a 2D array but provides a 1D array initializer. The correct syntax requires two dimensions, e.g., new int[3,3]. The compiler error CS0029 indicates cannot implicitly convert type 'int[]' to 'int[,]'.

❓ Predict Output

advanced

Output after checking for edge existence

What is the output of the following code that checks if an edge exists from node 0 to node 2 in a directed graph?

DSA C#

int[,] matrix = new int[3, 3];
matrix[0, 1] = 1;
matrix[1, 2] = 1;
if (matrix[0, 2] == 1) {
    Console.WriteLine("Edge exists");
} else {
    Console.WriteLine("No edge");
}

A Edge exists

B 0

C No edge

D 1

💡 Hint

Check if matrix[0,2] was set to 1 or not.

Only edges 0->1 and 1->2 are set. matrix[0,2] remains 0, so the else branch runs printing 'No edge'.

🧠 Conceptual

expert

Memory usage comparison of adjacency matrix vs adjacency list

For a graph with 1000 nodes and 10 edges, which statement about memory usage is correct?

A Adjacency list uses more memory than adjacency matrix

B Adjacency matrix uses significantly more memory than adjacency list

C Both use the same amount of memory

D Memory usage depends only on number of edges, not nodes

💡 Hint

Think about how adjacency matrix stores all possible edges.

Adjacency matrix stores a 1000x1000 matrix (1,000,000 entries), mostly zeros, while adjacency list stores only actual edges (10 entries). So matrix uses much more memory.

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