Adjacency Matrix Representation in DSA Python - Build from Scratch

Adjacency Matrix Representation

📖 Scenario: You are working on a simple social network where each person can be connected to others as friends. We want to represent these connections using an adjacency matrix, which is a way to show who is friends with whom in a grid of 0s and 1s.

🎯 Goal: Build an adjacency matrix for a small group of 4 people to show their friendship connections.

📋 What You'll Learn

Create a 4x4 adjacency matrix with exact values

Add a variable to store the number of people

Use a nested loop to print the adjacency matrix row by row

Print the adjacency matrix in a clear format

💡 Why This Matters

🌍 Real World

Adjacency matrices are used in social networks, maps, and computer networks to show connections between nodes or people.

💼 Career

Understanding adjacency matrices helps in roles involving graph algorithms, network analysis, and data structure design.

1

Create the adjacency matrix

Create a variable called adjacency_matrix that is a 4x4 list of lists with these exact values: [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 0], [0, 1, 0, 0]]

DSA Python

# Your code here

Hint

Think of the matrix as a list of 4 lists, each with 4 numbers (0 or 1).

2

Add the number of people variable

Create a variable called num_people and set it to 4 to represent the number of people in the network.

DSA Python

adjacency_matrix = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 0], [0, 1, 0, 0]]
# Your code here

Hint

This variable helps us know how many rows and columns the matrix has.

3

Print the adjacency matrix row by row

Use a for loop with variable i that runs from 0 to num_people - 1. Inside it, use another for loop with variable j that runs from 0 to num_people - 1. Print each element adjacency_matrix[i][j] followed by a space, and after the inner loop ends, print a new line.

DSA Python

adjacency_matrix = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 0], [0, 1, 0, 0]]
num_people = 4
# Your code here

Hint

Use nested loops to go through each row and column, printing values with spaces and new lines.

4

Display the adjacency matrix

Run the program to print the adjacency matrix exactly as shown, with each row on a new line and numbers separated by spaces.

DSA Python

adjacency_matrix = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 0], [0, 1, 0, 0]]
num_people = 4
for i in range(num_people):
    for j in range(num_people):
        print(adjacency_matrix[i][j], end=' ')
    print()
# Run the program to see the output

Hint

The output should show 4 rows with 4 numbers each, separated by spaces.

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