Adjacency List vs Matrix When to Choose Which in DSA C - Build Both Approaches

Adjacency List vs Matrix When to Choose Which

📖 Scenario: Imagine you are helping a city planner who wants to represent roads between different neighborhoods. Some neighborhoods are connected directly by roads, and some are not. You want to help the planner choose the best way to store this road information in a computer.

🎯 Goal: You will create two ways to represent the roads between neighborhoods: one using an adjacency matrix and one using an adjacency list. Then, you will decide which way is better depending on how many roads there are.

📋 What You'll Learn

Create an adjacency matrix for 4 neighborhoods with given roads

Create an adjacency list for the same 4 neighborhoods with the same roads

Count the number of roads using the adjacency matrix

Print the adjacency matrix and adjacency list to compare

💡 Why This Matters

🌍 Real World

City planners, network engineers, and social network analysts use adjacency lists and matrices to represent connections between points or people.

💼 Career

Understanding these representations helps in optimizing storage and speed when working with graphs in software development, data analysis, and network design.

1

Create an adjacency matrix for 4 neighborhoods

Create a 4x4 integer array called adjMatrix initialized with zeros. Then set the following roads (edges) to 1: from neighborhood 0 to 1, from 0 to 2, from 1 to 2, and from 2 to 3.

DSA C

# Create a 4x4 adjacency matrix with zeros
# Set roads as described

Hint

Think of adjMatrix as a table where rows and columns represent neighborhoods. A 1 means a road exists.

2

Create an adjacency list for the same neighborhoods

Create an array of integer pointers called adjList with size 4. Also create an integer array called adjListSizes with size 4 to store the number of roads for each neighborhood. Initialize the adjacency list with the following roads: neighborhood 0 connects to 1 and 2, neighborhood 1 connects to 2, and neighborhood 2 connects to 3.

DSA C

int adjMatrix[4][4] = {0};
adjMatrix[0][1] = 1;
adjMatrix[0][2] = 1;
adjMatrix[1][2] = 1;
adjMatrix[2][3] = 1;

// Create adjacency list arrays
// Your code here

Hint

Each neighborhood has a list of neighbors it connects to. Use arrays for each list and store their sizes.

3

Count the number of roads using the adjacency matrix

Create an integer variable called roadCount and set it to 0. Use a nested for loop with variables i and j to go through adjMatrix. Increase roadCount by 1 every time you find a 1 in adjMatrix[i][j].

DSA C

int adjMatrix[4][4] = {0};
adjMatrix[0][1] = 1;
adjMatrix[0][2] = 1;
adjMatrix[1][2] = 1;
adjMatrix[2][3] = 1;

int neighbors0[] = {1, 2};
int neighbors1[] = {2};
int neighbors2[] = {3};
int neighbors3[] = {};

int* adjList[4] = {neighbors0, neighbors1, neighbors2, neighbors3};
int adjListSizes[4] = {2, 1, 1, 0};

// Count roads using adjMatrix
// Your code here

Hint

Look at each cell in the matrix. If it is 1, it means a road exists, so add to the count.

4

Print the adjacency matrix and adjacency list

Use printf to print the adjacency matrix in a 4x4 grid format. Then print the adjacency list by showing each neighborhood and its connected neighbors. Finally, print the total number of roads stored in roadCount.

DSA C

int adjMatrix[4][4] = {0};
adjMatrix[0][1] = 1;
adjMatrix[0][2] = 1;
adjMatrix[1][2] = 1;
adjMatrix[2][3] = 1;

int neighbors0[] = {1, 2};
int neighbors1[] = {2};
int neighbors2[] = {3};
int neighbors3[] = {};

int* adjList[4] = {neighbors0, neighbors1, neighbors2, neighbors3};
int adjListSizes[4] = {2, 1, 1, 0};

int roadCount = 0;
for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
        if (adjMatrix[i][j] == 1) {
            roadCount++;
        }
    }
}

// Print adjacency matrix and list
// Your code here

Hint

Print the matrix row by row, then print each neighborhood's list of neighbors. Finally, print the road count.