Adjacency Matrix Representation in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create an empty adjacency matrix for a graph with n vertices.

DSA Python

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

Drag options to blanks, or click blank then click option'

A0

Bn

C1

Dn-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 instead of n for the matrix size.

Using n-1 which creates a smaller matrix.

The adjacency matrix is a square matrix of size n x n, so the inner list comprehension must run n times.

2fill in blank

medium

Complete the code to add an edge from vertex u to vertex v in the adjacency matrix.

DSA Python

adj_matrix[[1]][v] = 1

Drag options to blanks, or click blank then click option'

A0

Bv

Cu

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping u and v indices.

Assigning 0 instead of 1.

To add an edge from u to v, set the matrix cell at row u and column v to 1.

3fill in blank

hard

Fix the error in the code to check if there is an edge from vertex x to vertex y.

DSA Python

if adj_matrix[[1]][y] == 1:
    print("Edge exists")

Drag options to blanks, or click blank then click option'

Ax

B1

C0

Dy

Attempts:

3 left

💡 Hint

Common Mistakes

Using y as the row index instead of x.

Comparing to 0 instead of 1.

To check the edge from x to y, use x as the row index and y as the column index.

4fill in blank

hard

Fill both blanks to create an adjacency matrix for an undirected graph by adding edges in both directions.

DSA Python

adj_matrix[[1]][v] = 1
adj_matrix[[2]][u] = 1

Drag options to blanks, or click blank then click option'

Au

Bv

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Adding edges only in one direction.

Using 0 or 1 as indices instead of vertices.

For undirected graphs, add edges both from u to v and from v to u.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps each vertex to a list of its neighbors using the adjacency matrix.

DSA Python

neighbors = {vertex: [i for i, val in enumerate(adj_matrix[[1]]) if val [2] 1] for vertex in range([3])}

Drag options to blanks, or click blank then click option'

Avertex

B==

Cn

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect variable names.

Using '!=' instead of '==' to check edges.

Using wrong range for vertices.

The comprehension iterates over each vertex, then over its adjacency row to find neighbors where the value is 1.

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