Adjacency Matrix Representation in DSA C++ - Time & Space Complexity

Time Complexity: Adjacency Matrix Representation

O(1)

Understanding Time Complexity

We want to understand how the time to check or add connections in a graph grows as the graph gets bigger.

How does the size of the graph affect the work done using an adjacency matrix?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Check if edge exists between two nodes
bool hasEdge(int u, int v, int n, int matrix[][100]) {
    if (u < 0 || v < 0 || u >= n || v >= n) return false;
    return matrix[u][v] == 1;
}

// Add an edge between two nodes
void addEdge(int u, int v, int matrix[][100]) {
    matrix[u][v] = 1;
    matrix[v][u] = 1; // for undirected graph
}
    

This code checks if an edge exists and adds an edge between two nodes using an adjacency matrix.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing a single cell in the matrix to check or set an edge.
• How many times: Each operation accesses exactly one or two cells, no loops involved here.

How Execution Grows With Input

Checking or adding one edge always takes the same small amount of work, no matter how big the graph is.

Input Size (n)	Approx. Operations
10	1 or 2 matrix accesses
100	1 or 2 matrix accesses
1000	1 or 2 matrix accesses

Pattern observation: The work stays the same regardless of graph size for single edge operations.

Final Time Complexity

Time Complexity: O(1)

This means checking or adding an edge takes the same small amount of time no matter how big the graph is.

Common Mistake

[X] Wrong: "Checking if an edge exists takes longer as the graph grows because the matrix is bigger."

[OK] Correct: We only look at one spot in the matrix, so the size of the matrix does not affect the time for this operation.

Interview Connect

Understanding this helps you explain why adjacency matrices are great for quick edge checks, which is a useful skill in graph problems.

Self-Check

"What if we wanted to check all edges connected to one node? How would the time complexity change?"

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