Adjacency Matrix Representation in DSA Python - 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 Python

n = 3
adj_matrix = [[0]*n for _ in range(n)]

# Add edges
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1
adj_matrix[1][2] = 1
adj_matrix[2][1] = 1
adj_matrix[2][0] = 1
adj_matrix[0][2] = 1

for row in adj_matrix:
    print(row)

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

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

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

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

💡 Hint

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

Since the graph is undirected, each edge is represented twice symmetrically in the matrix. Adding edges 0-1, 1-2, and 2-0 sets those pairs to 1 in both directions.

❓ Predict Output

intermediate

Output of adjacency matrix for directed graph

What is the printed adjacency matrix after adding directed edges from node 0 to 1, and from node 1 to 2 in a graph with 3 nodes?

DSA Python

n = 3
adj_matrix = [[0]*n for _ in range(n)]

# Add directed edges
adj_matrix[0][1] = 1
adj_matrix[1][2] = 1

for row in adj_matrix:
    print(row)

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

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

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

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

💡 Hint

Directed edges only set one direction in the matrix.

Directed edges set the matrix entry from source to destination to 1 only. So 0->1 and 1->2 are set, others remain 0.

🧠 Conceptual

advanced

Memory usage of adjacency matrix vs adjacency list

Which statement correctly compares memory usage between adjacency matrix and adjacency list for a graph with n nodes and e edges?

A Adjacency matrix uses O(n + e) memory, adjacency list uses O(n^2).

B Adjacency matrix always uses O(n^2) memory regardless of edges, adjacency list uses O(n + e).

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

D Adjacency matrix uses O(e) memory, adjacency list uses O(n^2).

💡 Hint

Think about how adjacency matrix stores all possible edges.

Adjacency matrix stores a fixed n x n matrix, so memory is O(n^2). Adjacency list stores only existing edges, so memory is O(n + e).

🔧 Debug

advanced

Identify the error in adjacency matrix edge addition

What error will this code produce when adding an edge in an undirected graph with 3 nodes? Code: n = 3 adj_matrix = [[0]*n for _ in range(n)] # Add edge between 0 and 3 adj_matrix[0][3] = 1 adj_matrix[3][0] = 1

A IndexError: list index out of range

B TypeError: list indices must be integers

C No error, code runs fine

D KeyError: 3

💡 Hint

Check the valid indices for a list of size 3.

Index 3 is out of range for a list of size 3 (indices 0,1,2). Accessing adj_matrix[0][3] causes IndexError.

🚀 Application

expert

Number of edges in an undirected graph from adjacency matrix

Given the adjacency matrix below for an undirected graph, how many edges does the graph have? adj_matrix = [ [0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0] ]

A 2

B 6

C 8

D 4

💡 Hint

Count the number of 1s above the main diagonal.

In an undirected graph adjacency matrix, edges are counted by summing 1s above the diagonal. Here, edges are (0-1), (0-3), (1-2), (2-3) totaling 4 edges.

Practice

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

easy

A. A 2D array showing connections between nodes

B. A list of nodes in the graph

C. A sequence of edges in the graph

D. A tree structure of 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 yes, 0 for no).

3. Final Answer:

   A 2D array showing connections between nodes -> Option A

4. Quick Check:

   Adjacency matrix = 2D array of connections [OK]

Hint: Adjacency matrix is always a 2D grid of node links [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of connections
• Assuming it is a list or sequence

2. Which of the following is the correct way to declare a 3x3 adjacency matrix in Python initialized with zeros?

easy

A. matrix = [0,0,0]

B. matrix = [[0]*3]*3

C. matrix = [0]*3

D. matrix = [[0 for _ in range(3)] for _ in range(3)]

Solution

1. Step 1: Understand correct 2D list initialization

   Using list comprehension creates independent inner lists for each row.

2. Step 2: Analyze each option

   matrix = [[0]*3]*3 creates shallow copies causing all rows to reference the same list, which is incorrect. matrix = [[0 for _ in range(3)] for _ in range(3)] correctly creates separate lists. Options C and D create 1D lists, not 2D.

3. Final Answer:

   matrix = [[0 for _ in range(3)] for _ in range(3)] -> Option D

4. Quick Check:

   Use list comprehension for independent rows [OK]

Hint: Use nested list comprehension for 2D matrix [OK]

Common Mistakes:

• Using [[0]*3]*3 causes all rows to be same object
• Creating 1D list instead of 2D
• Forgetting to nest loops for rows and columns

3. What will be the output of the following code?

graph = [[0,1,0],[1,0,1],[0,1,0]]
for i in range(3):
    for j in range(3):
        if graph[i][j] == 1:
            print(f"Edge between {i} and {j}")

medium

A. Edge between 0 and 0
Edge between 1 and 1
Edge between 2 and 2

B. Edge between 0 and 1
Edge between 1 and 0
Edge between 1 and 2
Edge between 2 and 1

C. Edge between 0 and 1
Edge between 1 and 2

D. No output

Solution

1. Step 1: Analyze the adjacency matrix

   Matrix shows edges: (0,1), (1,0), (1,2), (2,1) as 1s.

2. Step 2: Trace nested loops and print statements

   Loops check each cell; when value is 1, print edge between i and j.

3. Final Answer:

   Edge between 0 and 1 Edge between 1 and 0 Edge between 1 and 2 Edge between 2 and 1 -> Option B

4. Quick Check:

   Print edges where matrix cell is 1 [OK]

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

Common Mistakes:

• Ignoring symmetric edges in undirected graph
• Printing only one direction of edges
• Confusing indices i and j

4. Find the error in the following code that tries to create an adjacency matrix for 4 nodes:

n = 4
matrix = [[0]*n]*n
matrix[0][1] = 1
print(matrix)

medium

A. The matrix initialization causes all rows to be the same list

B. The print statement syntax is incorrect

C. The index 1 is out of range for the matrix

D. The matrix should be initialized with ones, not zeros

Solution

1. Step 1: Understand matrix initialization

   Using [[0]*n]*n creates shallow copies; all rows point to the same list.

2. Step 2: Effect of modifying one element

   Changing matrix[0][1] changes that column in all rows because they share the same list.

3. Final Answer:

   The matrix initialization causes all rows to be the same list -> Option A

4. Quick Check:

   Use nested list comprehension to avoid shared rows [OK]

Hint: Avoid [[0]*n]*n; use nested list comprehension [OK]

Common Mistakes:

• Assuming rows are independent lists
• Ignoring shared reference problem
• Thinking print syntax is wrong

5. Given a directed graph with 3 nodes and edges: 0->1, 1->2, and 2->0, which adjacency matrix correctly represents it?

hard

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

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

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

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

Solution

1. Step 1: Map edges to matrix positions

   Edge 0->1 means matrix[0][1] = 1, 1->2 means matrix[1][2] = 1, 2->0 means matrix[2][0] = 1.

2. Step 2: Check each option against edges

   [[0,1,0],[0,0,1],[1,0,0]] matches these exactly; others have extra or missing edges.

3. Final Answer:

   [[0,1,0],[0,0,1],[1,0,0]] -> Option C

4. Quick Check:

   Edges map to 1s in correct matrix cells [OK]

Hint: Set matrix[i][j] = 1 for edge i->j only [OK]

Common Mistakes:

• Confusing directed and undirected edges
• Setting symmetric edges for directed graph
• Misplacing 1s in wrong matrix cells