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

Need a 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

Need a 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

Need a 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

Need a hint?

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