Adjacency Matrix Representation in DSA Python

Mental Model

Use a square grid to show which nodes connect directly to which others by marking spots with 1 or 0.

Analogy: Imagine a city map where each intersection is a node, and a big table shows if you can drive directly from one intersection to another by marking yes or no.

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Dry Run Walkthrough

Input: Graph with 3 nodes: edges between 0-1 and 1-2

Goal: Show the connections between nodes using a matrix where 1 means connected and 0 means not connected

Step 1: Create a 3x3 matrix filled with zeros

   0 1 2
0 [0 0 0]
1 [0 0 0]
2 [0 0 0]

Why: Start with no connections marked

Step 2: Mark connection between node 0 and node 1

   0 1 2
0 [0 1 0]
1 [1 0 0]
2 [0 0 0]

Why: Nodes 0 and 1 are connected, so mark both [0][1] and [1][0] as 1

Step 3: Mark connection between node 1 and node 2

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Why: Nodes 1 and 2 are connected, so mark both [1][2] and [2][1] as 1

Result:

   0 1 2
0 [0 1 0]
1 [1 0 1]
2 [0 1 0]

Annotated Code

DSA Python

class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0]*size for _ in range(size)]

    def add_edge(self, u, v):
        self.matrix[u][v] = 1  # mark connection from u to v
        self.matrix[v][u] = 1  # mark connection from v to u (undirected)

    def __str__(self):
        result = '   ' + ' '.join(str(i) for i in range(self.size)) + '\n'
        for i in range(self.size):
            result += str(i) + ' ' + str(self.matrix[i]) + '\n'
        return result

# Driver code
graph = Graph(3)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
print(graph)

self.matrix = [[0]*size for _ in range(size)]

initialize matrix with zeros for no connections

self.matrix[u][v] = 1 # mark connection from u to v

mark edge from node u to node v

self.matrix[v][u] = 1 # mark connection from v to u (undirected)

mark edge from node v to node u for undirected graph

Output

   0 1 2

0 [0, 1, 0]

1 [1, 0, 1]

2 [0, 1, 0]

Complexity Analysis

Time: O(1) for adding an edge because we directly access matrix cells

Space: O(n^2) because we store a matrix of size n by n for n nodes

vs Alternative: Compared to adjacency lists, adjacency matrix uses more space but allows faster edge checks

Edge Cases

Empty graph with zero nodes

Matrix is empty, no edges can be added

DSA Python

self.matrix = [[0]*size for _ in range(size)]

Graph with one node and no edges

Matrix is 1x1 with zero, no connections

DSA Python

self.matrix = [[0]*size for _ in range(size)]

When to Use This Pattern

When you need to quickly check if two nodes are connected and the graph is small or dense, use adjacency matrix for constant time edge lookup.

Common Mistakes

Mistake: Forgetting to mark both [u][v] and [v][u] for undirected graphs
Fix: Always update both positions in the matrix to keep symmetry

Mistake: Using adjacency matrix for very large sparse graphs causing high memory use
Fix: Use adjacency list instead for large sparse graphs

Summary

It shows graph connections using a square grid where 1 means connected and 0 means not.

Use it when you want fast checks if two nodes connect and the graph is not too big.

The key is that each cell in the matrix directly answers if two nodes share an edge.

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