Graph representations (adjacency matrix vs list) in Data Structures Theory - Hands-On Comparison

Graph representations (adjacency matrix vs list)

📖 Scenario: You are helping a friend understand how to represent a simple network of cities connected by roads. Each city is a point, and roads connect pairs of cities. You will create two common ways to show these connections: an adjacency matrix and an adjacency list.

🎯 Goal: Build two data structures for the same graph: one using an adjacency matrix and one using an adjacency list. This will help you see how the same information can be stored differently.

📋 What You'll Learn

Create a graph with exactly 4 cities named 'A', 'B', 'C', and 'D'.

Represent the connections between cities as given: A connected to B and C, B connected to C, and C connected to D.

Create an adjacency matrix showing these connections with 1 for connected and 0 for not connected.

Create an adjacency list showing the same connections with each city listing its connected neighbors.

💡 Why This Matters

🌍 Real World

Graph representations are used in maps, social networks, and computer networks to show how points connect.

💼 Career

Understanding graph data structures is important for software developers, data scientists, and network engineers to model and analyze relationships.

1

Create the list of cities

Create a list called cities with the exact city names: 'A', 'B', 'C', and 'D'.

Data Structures Theory

# Create the list of cities
# Your code here

Hint

Use a Python list with the city names as strings inside square brackets.

2

Set up the adjacency matrix

Create a variable called adjacency_matrix that is a 4x4 list of lists filled with zeros. This will hold connection info between cities.

Data Structures Theory

cities = ['A', 'B', 'C', 'D']
# Create a 4x4 matrix filled with 0
# Your code here

Hint

Use a nested list comprehension to create a 4 by 4 matrix filled with zeros.

3

Fill the adjacency matrix with connections

Update adjacency_matrix to show these connections: A connected to B and C, B connected to C, and C connected to D. Use 1 for connected pairs. Use the city indexes in cities to set the right matrix cells.

Data Structures Theory

cities = ['A', 'B', 'C', 'D']
adjacency_matrix = [[0 for _ in range(4)] for _ in range(4)]
# Set connections in adjacency_matrix
# Your code here

Hint

Use the indexes of cities in the list to mark connections with 1 in the matrix.

4

Create the adjacency list

Create a dictionary called adjacency_list where each city key maps to a list of connected cities as strings. Use the same connections: A connected to B and C, B connected to C, and C connected to D.

Data Structures Theory

cities = ['A', 'B', 'C', 'D']
adjacency_matrix = [[0 for _ in range(4)] for _ in range(4)]
adjacency_matrix[0][1] = 1  # A to B
adjacency_matrix[0][2] = 1  # A to C
adjacency_matrix[1][2] = 1  # B to C
adjacency_matrix[2][3] = 1  # C to D
# Create adjacency_list dictionary
# Your code here

Hint

Use a dictionary with city names as keys and lists of connected city names as values.

Practice

1. Which graph representation uses a 2D grid to show connections between nodes?

easy

A. Incidence matrix

B. Adjacency matrix

C. Edge list

D. Adjacency list

Solution

1. Step 1: Understand adjacency matrix structure

   An adjacency matrix is a 2D grid where rows and columns represent nodes, and cells show if an edge exists.

2. Step 2: Compare with other representations

   Adjacency lists store neighbors in lists, not grids. Edge lists and incidence matrices differ in format.

3. Final Answer:

   Adjacency matrix -> Option B

4. Quick Check:

   2D grid = adjacency matrix [OK]

Hint: Matrix means grid; list means neighbors [OK]

Common Mistakes:

• Confusing adjacency list with matrix
• Thinking edge list is a grid
• Mixing incidence matrix with adjacency matrix

2. Which of the following is the correct way to represent an adjacency list in Python?

easy

A. graph = [[1, 2], 0, [0, 1]]

B. graph = [[0,1,0],[1,0,1],[0,1,0]]

C. graph = [(0,1), (1,2), (2,0)]

D. graph = {0: [1, 2], 1: [0], 2: [0, 1]}

Solution

1. Step 1: Identify adjacency list format

   An adjacency list maps each node to a list of its neighbors, often using a dictionary in Python.

2. Step 2: Check each option

   graph = {0: [1, 2], 1: [0], 2: [0, 1]} uses a dictionary with keys as nodes and values as neighbor lists, which is correct. graph = [[0,1,0],[1,0,1],[0,1,0]] is a matrix, C is an edge list, D incorrectly uses an integer 0 for node 1 instead of a list.

3. Final Answer:

   graph = {0: [1, 2], 1: [0], 2: [0, 1]} -> Option D

4. Quick Check:

   Dict with neighbors = adjacency list [OK]

Hint: Adjacency list uses dict with node keys [OK]

Common Mistakes:

• Choosing matrix format as list
• Confusing edge list with adjacency list
• Using integer instead of list for neighbors

3. Given the adjacency matrix below, which nodes are connected to node 1?
graph = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]

medium

A. Nodes 0 and 2

B. Nodes 1 and 2

C. Nodes 0 and 1

D. Nodes 2 only

Solution

1. Step 1: Locate row for node 1

   Row 1 in the matrix is [1, 0, 1], representing edges from node 1 to nodes 0, 1, and 2.

2. Step 2: Identify connected nodes

   Values 1 indicate connection. Here, positions 0 and 2 have 1, so node 1 connects to nodes 0 and 2.

3. Final Answer:

   Nodes 0 and 2 -> Option A

4. Quick Check:

   Row 1 has 1s at 0 and 2 [OK]

Hint: Check row for node, 1 means connected [OK]

Common Mistakes:

• Confusing row and column indices
• Including node itself as connected
• Misreading zeros as edges

4. What is wrong with this adjacency list representation?
graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: 1}

medium

A. Node 3's neighbors should be in a list

B. Node 1 has an invalid neighbor

C. Node 0 should not have neighbors

D. The graph should be an adjacency matrix

Solution

1. Step 1: Check format of neighbors for each node

   Nodes 0, 1, and 2 have neighbor lists. Node 3 has a single integer instead of a list.

2. Step 2: Identify correct adjacency list format

   Neighbors must always be in a list, even if only one neighbor exists, to keep consistent structure.

3. Final Answer:

   Node 3's neighbors should be in a list -> Option A

4. Quick Check:

   Neighbors must be lists [OK]

Hint: Neighbors always in lists, never single values [OK]

Common Mistakes:

• Ignoring single neighbor format
• Thinking adjacency list must be matrix
• Assuming neighbors can be integers

5. For a graph with 1000 nodes and only 10,000 edges, which representation is more memory efficient and why?

hard

A. Adjacency matrix, because it allows faster edge checks

B. Adjacency matrix, because it uses fixed size memory

C. Adjacency list, because it stores only existing edges

D. Adjacency list, because it stores all possible edges

Solution

1. Step 1: Calculate memory use for adjacency matrix

   An adjacency matrix for 1000 nodes uses 1000x1000 = 1,000,000 cells, regardless of edges.

2. Step 2: Calculate memory use for adjacency list

   An adjacency list stores only the 10,000 edges, so memory use is proportional to edges, much less than matrix.

3. Step 3: Compare efficiency

   Since edges are sparse compared to possible connections, adjacency list is more memory efficient.

4. Final Answer:

   Adjacency list, because it stores only existing edges -> Option C

5. Quick Check:

   Sparse graph = adjacency list efficient [OK]

Hint: Sparse graph? Use adjacency list for less memory [OK]

Common Mistakes:

• Choosing matrix for sparse graphs
• Confusing speed with memory use
• Thinking adjacency list stores all edges