Adjacency Matrix Representation in DSA Python - Execution Trace

Concept Flow - Adjacency Matrix Representation

Start

↓

Create NxN matrix

↓

Initialize all cells to 0

↓

For each edge (u,v)

↓

Set matrix[u

↓

If undirected, set matrix[v

↓

Matrix ready to represent graph

↓

Use matrix for graph operations

↓

End

Build a square matrix where each cell shows if an edge exists between two nodes, marking 1 for edges and 0 for no edges.

Execution Sample

DSA Python

nodes = 3
matrix = [[0]*nodes for _ in range(nodes)]
matrix[0][1] = 1
matrix[1][2] = 1
matrix[2][0] = 1

Create a 3-node graph adjacency matrix and add edges 0->1, 1->2, 2->0.

Execution Table

Step	Operation	Nodes in Graph	Matrix State	Visual State
1	Create 3x3 matrix initialized to 0	3	[[0,0,0],[0,0,0],[0,0,0]]	0 0 0 0 0 0 0 0 0
2	Add edge 0->1	3	[[0,1,0],[0,0,0],[0,0,0]]	0 1 0 0 0 0 0 0 0
3	Add edge 1->2	3	[[0,1,0],[0,0,1],[0,0,0]]	0 1 0 0 0 1 0 0 0
4	Add edge 2->0	3	[[0,1,0],[0,0,1],[1,0,0]]	0 1 0 0 0 1 1 0 0
5	End of operations	3	[[0,1,0],[0,0,1],[1,0,0]]	0 1 0 0 0 1 1 0 0

💡 All edges added, matrix fully represents the graph.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
nodes	3	3	3	3	3	3
matrix	undefined	[[0,0,0],[0,0,0],[0,0,0]]	[[0,1,0],[0,0,0],[0,0,0]]	[[0,1,0],[0,0,1],[0,0,0]]	[[0,1,0],[0,0,1],[1,0,0]]	[[0,1,0],[0,0,1],[1,0,0]]

Key Moments - 3 Insights

Why do we initialize the matrix with zeros?

Because zeros mean no edges between nodes initially, as shown in Step 1 of the execution_table where the matrix is all zeros.

Why do we set matrix[u][v] = 1 when adding an edge?

Setting matrix[u][v] = 1 marks that there is an edge from node u to node v, as seen in Steps 2-4 where edges are added.

How does the matrix represent an undirected graph differently?

For undirected graphs, both matrix[u][v] and matrix[v][u] are set to 1, but here only one direction is set, indicating a directed graph (see Steps 2-4).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of matrix[1][2]?

A 1

B 0

C 2

D Undefined

💡 Hint

Check the 'Matrix State' column at Step 3 in the execution_table.

At which step does the edge from node 2 to node 0 get added?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Operation' column in the execution_table for when matrix[2][0] changes.

If we add an edge from node 1 to node 0 in this matrix, what will matrix[1][0] be after?

A 0

B 1

C 2

D Undefined

💡 Hint

Adding an edge sets the corresponding matrix cell to 1, as shown in Steps 2-4.

Concept Snapshot

Adjacency Matrix:
- Use NxN matrix for N nodes
- matrix[i][j] = 1 means edge from i to j
- Initialize all cells to 0
- For undirected graphs, set both matrix[i][j] and matrix[j][i]
- Easy to check edge existence in O(1) time

Full Transcript

Adjacency matrix representation uses a square matrix to show edges between nodes. We start by creating an NxN matrix filled with zeros, meaning no edges. Then for each edge from node u to node v, we set matrix[u][v] to 1. This marks the presence of an edge. For undirected graphs, both matrix[u][v] and matrix[v][u] are set to 1. This method allows quick checks if an edge exists between any two nodes by looking at the matrix cell. The example shows a 3-node graph with edges 0->1, 1->2, and 2->0 added step-by-step, updating the matrix accordingly.

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