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 graph[3][3] = {0};
graph[0][1] = 1;
graph[1][0] = 1;
graph[1][2] = 1;
graph[2][1] = 1;
graph[2][0] = 1;
graph[0][2] = 1;
for(int i=0; i<3; i++) {
  for(int j=0; j<3; j++) {
    std::cout << graph[i][j] << " ";
  }
  std::cout << std::endl;
}

A [[0,0,0],[0,0,0],[0,0,0]]

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

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

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

💡 Hint

Remember that for an undirected graph, edges are symmetric in the adjacency matrix.

Edges between nodes 0-1, 1-2, and 2-0 set the corresponding matrix entries to 1 symmetrically. So positions (0,1), (1,0), (1,2), (2,1), (2,0), and (0,2) are 1, others 0.

❓ Predict Output

intermediate

Output of adjacency matrix for directed graph

What is the adjacency matrix output after adding directed edges 0->1, 1->2, and 2->0 in a graph with 3 nodes?

DSA C++

int graph[3][3] = {0};
graph[0][1] = 1;
graph[1][2] = 1;
graph[2][0] = 1;
for(int i=0; i<3; i++) {
  for(int j=0; j<3; j++) {
    std::cout << graph[i][j] << " ";
  }
  std::cout << std::endl;
}

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

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

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

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

💡 Hint

Directed edges only set one direction in the matrix.

Edges 0->1, 1->2, and 2->0 set graph[0][1], graph[1][2], and graph[2][0] to 1 respectively. Others remain 0.

🔧 Debug

advanced

Identify the error in adjacency matrix initialization

What error will this code produce when compiling or running? int graph[3][3]; for(int i=0; i<=3; i++) { for(int j=0; j<=3; j++) { graph[i][j] = 0; } }

DSA C++

int graph[3][3];
for(int i=0; i<=3; i++) {
  for(int j=0; j<=3; j++) {
    graph[i][j] = 0;
  }
}

A No error, runs fine

B Syntax error: missing semicolon

C Runtime error: Array index out of bounds

D Logical error: matrix not initialized

💡 Hint

Check the loop conditions and array size carefully.

The loops use i<=3 and j<=3 which tries to access graph[3][3], but valid indices are 0 to 2. This causes out of bounds access at runtime.

🧠 Conceptual

advanced

Memory usage of adjacency matrix vs adjacency list

Which statement correctly compares memory usage of adjacency matrix and adjacency list for a graph with V vertices and E edges?

A Adjacency matrix always uses O(V^2) memory regardless of edges; adjacency list uses O(V + E)

B Adjacency matrix uses O(V + E) memory; adjacency list uses O(V^2)

C Both adjacency matrix and adjacency list use O(V^2) memory

D Adjacency matrix uses O(E) memory; adjacency list uses O(V^2)

💡 Hint

Think about how adjacency matrix stores all possible edges.

Adjacency matrix stores a VxV matrix, so memory is O(V^2) always. Adjacency list stores only existing edges, so memory is O(V + E).

🚀 Application

expert

Find if graph is complete using adjacency matrix

Given an undirected graph with V nodes represented by an adjacency matrix, which code snippet correctly checks if the graph is complete (every pair of distinct nodes connected)?

A

for(int i=0; i<V; i++) {
  for(int j=0; j<V; j++) {
    if(i != j && graph[i][j] == 0) return false;
  }
}
return true;

B

for(int i=0; i<V; i++) {
  for(int j=0; j<V; j++) {
    if(graph[i][j] == 0) return false;
  }
}
return true;

C

for(int i=0; i<V; i++) {
  for(int j=0; j<V; j++) {
    if(i == j && graph[i][j] == 0) return false;
  }
}
return true;

D

for(int i=0; i<V; i++) {
  if(graph[i][i] == 1) return false;
}
return true;

💡 Hint

A complete graph has edges between every pair of different nodes.

We must check all pairs (i,j) where i != j to ensure graph[i][j] == 1. Option A correctly does this. Option A wrongly checks diagonal too. Options A and D check diagonal incorrectly.

Practice

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

easy

A. A sequence of visited nodes

B. A list of nodes in the graph

C. A 2D array showing connections between nodes

D. A stack used for graph traversal

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 C

4. Quick Check:

   Adjacency matrix = 2D array of connections [OK]

Hint: Adjacency matrix = grid showing edges between nodes [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare a 4x4 adjacency matrix in C++?

easy

A. int matrix(4,4);

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

C. int matrix[4];

D. int matrix[4][4];

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, a 2D array is declared as type name[size1][size2].

2. Step 2: Check each option

   int matrix[4][4]; uses correct syntax: int matrix[4][4]; int matrix(4,4); is invalid syntax, C is 1D array, D is invalid in C++.

3. Final Answer:

   int matrix[4][4]; -> Option D

4. Quick Check:

   2D array declaration = int matrix[4][4]; [OK]

Hint: Use int name[rows][cols] for 2D arrays in C++ [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Declaring only one dimension
• Trying Java-style new keyword in C++

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

int graph[3][3] = {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};

What is the output of this code snippet?

for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++) {
    if (graph[i][j] == 1) {
      std::cout << i << "->" << j << " ";
    }
  }
}

medium

A. 0->1 1->0 1->2 2->1

B. 0->0 1->1 2->2

C. 1->0 2->1

D. 0->2 2->0

Solution

1. Step 1: Analyze the adjacency matrix values

   Matrix shows edges: 0 connected to 1, 1 connected to 0 and 2, 2 connected to 1.

2. Step 2: Trace the nested loops and print statements

   For each i,j where graph[i][j] == 1, print i->j. This matches edges 0->1, 1->0, 1->2, 2->1.

3. Final Answer:

   0->1 1->0 1->2 2->1 -> Option A

4. Quick Check:

   Edges printed = 0->1 1->0 1->2 2->1 [OK]

Hint: Print edges where matrix cell is 1 [OK]

Common Mistakes:

• Ignoring symmetric edges in undirected graph
• Printing zeros as edges
• Mixing row and column indices

4. Identify the error in this adjacency matrix initialization code for a graph with 2 nodes:

int graph[2][2] = {
  {0, 1},
  {1}
};

medium

A. Second row has missing element

B. Matrix size is incorrect

C. Values should be boolean, not int

D. Initialization syntax is correct

Solution

1. Step 1: Check each row's initialization length

   First row has 2 elements: {0,1}. Second row has only 1 element: {1}.

2. Step 2: Understand 2D array initialization rules

   Each row must have exactly 2 elements to match declared size. Missing element causes error.

3. Final Answer:

   Second row has missing element -> Option A

4. Quick Check:

   Each row must match declared column size [OK]

Hint: Each row must have same number of elements as columns [OK]

Common Mistakes:

• Assuming partial row initialization is allowed
• Confusing matrix size with data type
• Ignoring compiler error messages

5. You have a directed graph with 4 nodes represented by this adjacency matrix:

int graph[4][4] = {
  {0, 1, 0, 0},
  {0, 0, 1, 0},
  {0, 0, 0, 1},
  {1, 0, 0, 0}
};

Write a function in C++ that returns true if there is an edge from node u to node v, false otherwise. Which of these is correct?

hard

A. bool hasEdge(int u, int v) { return graph[v][u] == 1; }

B. bool hasEdge(int u, int v) { return graph[u][v] == 1; }

C. bool hasEdge(int u, int v) { return graph[u][v] == 0; }

D. bool hasEdge(int u, int v) { return graph[u] == graph[v]; }

Solution

1. Step 1: Understand adjacency matrix indexing for edges

   graph[u][v] == 1 means edge from node u to node v exists.

2. Step 2: Check each function option

   bool hasEdge(int u, int v) { return graph[u][v] == 1; } correctly returns true if edge exists. bool hasEdge(int u, int v) { return graph[v][u] == 1; } reverses indices, C checks for no edge, D compares rows incorrectly.

3. Final Answer:

   bool hasEdge(int u, int v) { return graph[u][v] == 1; } -> Option B

4. Quick Check:

   Check graph[u][v] == 1 for edge presence [OK]

Hint: Check graph[u][v] == 1 for edge from u to v [OK]

Common Mistakes:

• Swapping u and v indices
• Checking for zero instead of one
• Comparing entire rows instead of single cell