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

Adjacency List vs Matrix When to Choose Which

📖 Scenario: Imagine you are helping a city planner represent roads between different neighborhoods. Some neighborhoods are connected directly by roads, and some are not. You want to store this information in a way that helps answer questions like "Is there a direct road between neighborhood A and B?" or "Which neighborhoods are connected to neighborhood C?"

🎯 Goal: You will create two ways to represent the connections between neighborhoods: an adjacency list and an adjacency matrix. Then, you will see how to choose which one to use based on the number of connections.

📋 What You'll Learn

Create an adjacency list for 4 neighborhoods with given connections

Create an adjacency matrix for the same neighborhoods and connections

Count the total number of roads (edges) in the graph

Print both adjacency list and adjacency matrix representations

💡 Why This Matters

🌍 Real World

City planners, network engineers, and game developers use adjacency lists and matrices to represent connections between points like roads, computers, or game characters.

💼 Career

Understanding when to use adjacency lists or matrices helps software developers and data scientists efficiently store and process graph data in real-world applications.

1

Create an adjacency list for neighborhoods

Create a variable called adjacencyList as an object where keys are neighborhood names 'A', 'B', 'C', and 'D'. Set the values as arrays of connected neighborhoods exactly as: 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B'].

DSA Typescript

# Your code here

Hint

Think of the adjacency list as a map where each neighborhood points to a list of neighborhoods it connects to directly.

2

Create an adjacency matrix for neighborhoods

Create a variable called adjacencyMatrix as a 2D array of numbers representing connections between neighborhoods 'A', 'B', 'C', and 'D' in order. Use 1 for a direct road and 0 for no road. The matrix should be exactly: [[0,1,1,0],[1,0,0,1],[1,0,0,0],[0,1,0,0]].

DSA Typescript

const adjacencyList: { [key: string]: string[] } = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A'],
  'D': ['B']
};
# Your code here

Hint

Think of the adjacency matrix as a grid where rows and columns represent neighborhoods in order A, B, C, D. Put 1 if connected, else 0.

3

Count total roads using adjacency list

Create a variable called totalRoads and set it to 0. Use a for loop with variables neighborhood and connections to iterate over Object.entries(adjacencyList). For each connections array, add its length to totalRoads. After the loop, divide totalRoads by 2 to avoid double counting roads.

DSA Typescript

const adjacencyList: { [key: string]: string[] } = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A'],
  'D': ['B']
};

const adjacencyMatrix: number[][] = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 0],
  [0, 1, 0, 0]
];

// Your code here

Hint

Each road is counted twice in the adjacency list (once from each neighborhood), so divide by 2 at the end.

4

Print adjacency list, matrix, and total roads

Use console.log to print the adjacencyList, then the adjacencyMatrix, and finally the totalRoads variable. Print each on its own line.

DSA Typescript

const adjacencyList: { [key: string]: string[] } = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A'],
  'D': ['B']
};

const adjacencyMatrix: number[][] = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 0],
  [0, 1, 0, 0]
];

let totalRoads = 0;
for (const [neighborhood, connections] of Object.entries(adjacencyList)) {
  totalRoads += connections.length;
}
totalRoads = totalRoads / 2;

// Your code here

Hint

Use console.log three times to print each variable on its own line.