Adjacency List Representation in DSA Typescript - Execution Trace

Concept Flow - Adjacency List Representation

Start

↓

Create empty adjacency list

↓

For each edge

↓

Add neighbor to source node list

↓

Add neighbor to destination node list (if undirected)

↓

Repeat for all edges

↓

Adjacency list ready

Build an adjacency list by adding neighbors for each node from the edges, storing connections efficiently.

Execution Sample

DSA Typescript

const graph = new Map<number, number[]>();
graph.set(1, [2, 3]);
graph.set(2, [1, 4]);
graph.set(3, [1]);
graph.set(4, [2]);

Create an adjacency list for a graph with 4 nodes and edges between them.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize empty Map	{}	None	{}
2	Add edge 1-2	{1: [], 2: []}	Add 2 to 1's list, 1 to 2's list	{1: [2], 2: [1]}
3	Add edge 1-3	{1: [2], 2: [1], 3: []}	Add 3 to 1's list, 1 to 3's list	{1: [2, 3], 2: [1], 3: [1]}
4	Add edge 2-4	{1: [2, 3], 2: [1], 3: [1], 4: []}	Add 4 to 2's list, 2 to 4's list	{1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}
5	All edges processed	{1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}	No changes	{1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}

💡 All edges added, adjacency list fully built

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
graph	{}	{1: [2], 2: [1]}	{1: [2, 3], 2: [1], 3: [1]}	{1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}	{1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}

Key Moments - 3 Insights

Why do we add neighbors to both nodes in an undirected graph?

Because edges connect two nodes both ways, so each node's list must include the other. See steps 2-4 in execution_table where both nodes update their lists.

What happens if a node has no edges?

It will have an empty list or no entry in the adjacency list. In this example, all nodes have edges, but an isolated node would just have an empty array or be missing.

Why use a Map instead of an array for adjacency list?

A Map allows flexible node keys (like numbers or strings) and easy insertion. Arrays require numeric continuous indices. This is shown in variable_tracker where graph is a Map.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what neighbors does node 1 have?

A [2]

B [2, 3]

C [3]

D [1, 3]

💡 Hint

Check the 'Visual State' column at step 3 in execution_table.

At which step does node 4 first appear in the adjacency list?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Nodes in List' column to see when node 4 is added.

If the graph was directed and edges only added from source to destination, how would node 2's list change after step 2?

A []

B [4]

C [1]

D [1, 4]

💡 Hint

In a directed graph, only source node's list updates. Check pointer changes in execution_table step 2.

Concept Snapshot

Adjacency List Representation:
- Use a Map or array to store nodes and their neighbors.
- For each edge, add destination to source's list.
- For undirected graphs, add source to destination's list too.
- Efficient for sparse graphs.
- Allows quick neighbor lookup.

Full Transcript

This visualization shows how to build an adjacency list for a graph. We start with an empty Map. For each edge, we add the connected nodes to each other's neighbor lists if the graph is undirected. The execution table tracks each step, showing how the adjacency list grows. The variable tracker shows the graph Map's state after each edge is added. Key moments clarify why neighbors are added both ways, what happens with isolated nodes, and why a Map is used. The quiz tests understanding of the adjacency list state at different steps and the difference if the graph was directed.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list of all nodes without connections

B. A matrix showing distances between nodes

C. A queue of nodes to visit next

D. A list where each node stores its connected neighbors

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each node with a list of its neighbors, showing direct connections.

2. Step 2: Compare options with definition

   Only A list where each node stores its connected neighbors correctly describes this structure; others describe different concepts.

3. Final Answer:

   A list where each node stores its connected neighbors -> Option D

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always stores neighbors per node [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores distances instead of neighbors
• Assuming it is a queue or unrelated structure

2. Which of the following is the correct TypeScript syntax to declare an adjacency list for a graph with nodes as numbers?

easy

A. const graph: number[][] = [];

B. const graph: Map = new Map();

C. const graph: Record = {};

D. const graph: Array<number> = [];

Solution

1. Step 1: Identify adjacency list type

   An adjacency list maps each node (number) to an array of connected nodes (number[]).

2. Step 2: Match TypeScript syntax

   Map correctly represents this; others are incorrect types or structures.

3. Final Answer:

   const graph: Map = new Map(); -> Option B

4. Quick Check:

   Map = adjacency list [OK]

Hint: Use Map with number keys and array values for adjacency list [OK]

Common Mistakes:

• Using Record which maps to single number, not array
• Using number[][] without keys for nodes
• Using Array<number> which is just a list, not adjacency

3. Given the following TypeScript code, what is the output after adding edges?

const graph: Map = new Map();
graph.set(1, [2, 3]);
graph.set(2, [1]);
graph.set(3, [1, 4]);
graph.set(4, [3]);
console.log(graph.get(3));

medium

A. [2, 3]

B. [3, 4]

C. [1, 4]

D. undefined

Solution

1. Step 1: Trace graph.set calls

   Node 3 is set with neighbors [1, 4].

2. Step 2: Check graph.get(3)

   Returns the array [1, 4] assigned to node 3.

3. Final Answer:

   [1, 4] -> Option C

4. Quick Check:

   graph.get(3) = [1, 4] [OK]

Hint: graph.get(node) returns neighbors array [OK]

Common Mistakes:

• Confusing neighbors of node 3 with node 1 or 2
• Expecting undefined if not careful with set calls
• Mixing up array contents order

4. Identify the error in this TypeScript adjacency list code snippet:

const graph: Map = new Map();
graph.set(1, [2]);
graph.set(2, [1]);
graph.get(3).push(1);

medium

A. graph.get(3) returns undefined, so push causes error

B. Map keys must be strings, not numbers

C. graph.set should use arrays of strings, not numbers

D. Missing initialization of graph variable

Solution

1. Step 1: Check graph.get(3) call

   Node 3 was never set, so graph.get(3) returns undefined.

2. Step 2: Understand push on undefined

   Calling push on undefined causes runtime error.

3. Final Answer:

   graph.get(3) returns undefined, so push causes error -> Option A

4. Quick Check:

   Accessing unset key returns undefined [OK]

Hint: Check if key exists before pushing to adjacency list [OK]

Common Mistakes:

• Assuming graph.get(3) returns empty array automatically
• Thinking Map keys must be strings (numbers are allowed)
• Ignoring runtime error from push on undefined

5. You want to represent a directed graph with nodes 1 to 4 using an adjacency list in TypeScript. Which code correctly adds an edge from node 2 to node 4 without affecting other edges?

const graph: Map = new Map();
graph.set(1, [2]);
graph.set(2, [3]);
graph.set(3, []);
graph.set(4, []);
// Add edge from 2 to 4 here

hard

A. graph.get(2)?.push(4);

B. graph.set(2, [4]);

C. graph.set(4, [2]);

D. graph.get(4)?.push(2);

Solution

1. Step 1: Understand existing edges

   Node 2 currently has neighbors [3]. We want to add 4 without removing 3.

2. Step 2: Choose correct method to add edge

   Using graph.get(2)?.push(4) adds 4 to existing array, preserving [3]. graph.set(2, [4]) replaces neighbors, removing 3.

3. Final Answer:

   graph.get(2)?.push(4); -> Option A

4. Quick Check:

   Use push to add edge without overwriting [OK]

Hint: Use push on existing neighbors to add edges safely [OK]

Common Mistakes:

• Overwriting neighbors array with set instead of pushing
• Adding edge to wrong node
• Confusing direction of edge in directed graph