Adjacency List Representation in DSA Javascript - Execution Trace

Concept Flow - Adjacency List Representation

Start with empty graph

↓

Add vertex to graph

↓

Add edge: vertex1 -> vertex2

↓

Update adjacency list for vertex1

↓

Repeat for all edges

↓

Graph represented as adjacency lists

Build graph by adding vertices and edges, updating adjacency lists for each vertex.

Execution Sample

DSA Javascript

const graph = {};
graph['A'] = ['B', 'C'];
graph['B'] = ['A', 'D'];
graph['C'] = ['A'];
graph['D'] = ['B'];

Create a graph with vertices A, B, C, D and edges between them using adjacency lists.

Execution Table

Step	Operation	Nodes in Graph	Adjacency List State	Visual State
1	Initialize empty graph	0	{}	{}
2	Add vertex 'A' with edges to B, C	1	{"A": ["B", "C"]}	A -> B, C
3	Add vertex 'B' with edges to A, D	2	{"A": ["B", "C"], "B": ["A", "D"]}	A -> B, C; B -> A, D
4	Add vertex 'C' with edge to A	3	{"A": ["B", "C"], "B": ["A", "D"], "C": ["A"]}	A -> B, C; B -> A, D; C -> A
5	Add vertex 'D' with edge to B	4	{"A": ["B", "C"], "B": ["A", "D"], "C": ["A"], "D": ["B"]}	A -> B, C; B -> A, D; C -> A; D -> B
6	All vertices and edges added	4	{"A": ["B", "C"], "B": ["A", "D"], "C": ["A"], "D": ["B"]}	Final adjacency list representation

💡 All vertices and edges are added, adjacency list fully represents the graph.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
graph	{}	{"A": ["B", "C"]}	{"A": ["B", "C"], "B": ["A", "D"]}	{"A": ["B", "C"], "B": ["A", "D"], "C": ["A"]}	{"A": ["B", "C"], "B": ["A", "D"], "C": ["A"], "D": ["B"]}	{"A": ["B", "C"], "B": ["A", "D"], "C": ["A"], "D": ["B"]}

Key Moments - 3 Insights

Why do we store neighbors in a list for each vertex?

Because the adjacency list shows which vertices are directly connected to each vertex, making it easy to find neighbors quickly as seen in steps 2-5.

What happens if a vertex has no edges?

Its adjacency list will be an empty list, meaning no neighbors. This is not shown here but would be like "E": [] if vertex E had no edges.

Why do we add edges for both vertices in an undirected graph?

Because each edge connects two vertices both ways, so each vertex's adjacency list must include the other, as shown in steps 2 and 3 where A includes B and B includes A.

Visual Quiz - 3 Questions

Look at the execution table, what is the adjacency list state after step 3?

A {"A": ["B", "C"], "B": ["A", "D"]}

B {"A": ["B"], "B": ["A", "D"]}

C {"A": ["B", "C"], "B": ["D"]}

D {"A": ["B", "C"], "C": ["A"]}

💡 Hint

Check the 'Adjacency List State' column in row with Step 3.

At which step does the graph first contain 3 vertices?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Nodes in Graph' column to see when it reaches 3.

If we add vertex 'E' with no edges, how would the adjacency list change?

A Add "E": null to the graph object

B Add "E": ["A"] to the graph object

C Add "E": [] to the graph object

D No change, vertex with no edges is not stored

💡 Hint

Vertices with no edges have empty lists in adjacency list representation.

Concept Snapshot

Adjacency List Representation:
- Graph stored as object/dictionary
- Each vertex key maps to list of neighbors
- Efficient for sparse graphs
- Add vertex by creating key
- Add edge by updating neighbor lists
- Undirected edges stored both ways

Full Transcript

Adjacency List Representation stores a graph as a collection of vertices, each with a list of neighbors. We start with an empty graph, add vertices as keys, and add edges by listing connected vertices. Each step updates the adjacency list, showing which vertices connect to which. This method is efficient for graphs with fewer edges. Vertices with no edges have empty lists. For undirected graphs, edges appear in both vertices' lists. The execution table shows step-by-step how the graph grows and how adjacency lists update.

Practice

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

easy

A. A list where each node stores its neighbors

B. A matrix showing connections between nodes

C. A list of all nodes without connections

D. A list of edges sorted by weight

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each node with a list of its neighbors or connected nodes.

2. Step 2: Compare with other graph representations

   An adjacency matrix is a 2D array, not a list of neighbors. Other options describe different structures.

3. Final Answer:

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

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always stores neighbors for each node [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores edges sorted by weight
• Assuming it lists nodes without connections only

2. Which of the following is the correct JavaScript syntax to initialize an empty adjacency list for a graph?

easy

A. const graph = [];

B. const graph = new Map();

C. const graph = {};

D. const graph = new Set();

Solution

1. Step 1: Identify suitable data structure for adjacency list

   An adjacency list can be implemented using a Map to store nodes and their neighbors efficiently.

2. Step 2: Check syntax correctness

   new Map() creates an empty map. Arrays or objects can be used but Map is preferred for graph keys. Set is for unique values, not key-value pairs.

3. Final Answer:

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

4. Quick Check:

   Use Map() for adjacency list initialization [OK]

Hint: Use Map() to store nodes and neighbors in adjacency list [OK]

Common Mistakes:

• Using Set which does not store key-value pairs
• Using empty array which is less clear for key-value
• Using empty object but Map is better for keys

3. Given the following adjacency list representation in JavaScript, what will be the output of console.log(graph.get('A'));?

const graph = new Map();
graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);
graph.set('C', ['A']);
graph.set('D', ['B']);

medium

A. ['B', 'D']

B. ['A', 'D']

C. ['C', 'D']

D. ['B', 'C']

Solution

1. Step 1: Locate the key 'A' in the adjacency list

   The graph Map has key 'A' with value ['B', 'C'] representing neighbors.

2. Step 2: Understand what graph.get('A') returns

   It returns the array of neighbors for 'A', which is ['B', 'C'].

3. Final Answer:

   ['B', 'C'] -> Option D

4. Quick Check:

   graph.get('A') = ['B', 'C'] [OK]

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

Common Mistakes:

• Confusing neighbors of 'A' with neighbors of 'B'
• Expecting a string instead of array
• Mixing up keys and values in Map

4. The following code attempts to add an edge from node 'A' to node 'D' in an adjacency list but has a bug. What is the error?

const graph = new Map();
graph.set('A', ['B', 'C']);
// Add edge from A to D
graph.get('A').push('D');
console.log(graph.get('A'));

medium

A. graph.get('A') returns undefined causing error

B. Cannot push to array returned by graph.get('A')

C. The code works correctly and adds 'D' to neighbors

D. graph.set should be used instead of push

Solution

1. Step 1: Check if graph.get('A') returns an array

   graph.get('A') returns ['B', 'C'], an array, so push is valid.

2. Step 2: Verify if push adds 'D' correctly

   push('D') adds 'D' to the array, so neighbors become ['B', 'C', 'D'].

3. Final Answer:

   The code works correctly and adds 'D' to neighbors -> Option C

4. Quick Check:

   push on neighbors array works [OK]

Hint: graph.get(node) returns array; push adds neighbor [OK]

Common Mistakes:

• Assuming graph.get returns undefined if key exists
• Thinking push cannot modify array in Map
• Confusing push with set method

5. You want to represent a directed graph with nodes 'X', 'Y', 'Z' where edges are X->Y, Y->Z, and Z->X. Which adjacency list correctly represents this graph in JavaScript?

hard

A. const graph = new Map([['X', ['Y']], ['Y', ['Z']], ['Z', ['X']]]);

B. const graph = new Map([['X', ['Y', 'Z']], ['Y', ['X']], ['Z', ['Y']]]);

C. const graph = new Map([['X', ['Z']], ['Y', ['X']], ['Z', ['Y']]]);

D. const graph = new Map([['X', ['Y']], ['Y', ['X', 'Z']], ['Z', []]]);

Solution

1. Step 1: Understand directed edges

   Edges are X->Y, Y->Z, Z->X, so each node points only to its direct neighbors.

2. Step 2: Match edges to adjacency list entries

   'X' neighbors: ['Y'], 'Y' neighbors: ['Z'], 'Z' neighbors: ['X'] matches const graph = new Map([['X', ['Y']], ['Y', ['Z']], ['Z', ['X']]]); exactly.

3. Final Answer:

   const graph = new Map([['X', ['Y']], ['Y', ['Z']], ['Z', ['X']]]); -> Option A

4. Quick Check:

   Directed edges match adjacency list neighbors [OK]

Hint: Each node's list shows only nodes it points to [OK]

Common Mistakes:

• Including neighbors that don't have edges from the node
• Mixing up direction of edges
• Adding extra neighbors not in edges