Adjacency List Representation in DSA Javascript - Build from Scratch

Adjacency List Representation

📖 Scenario: Imagine you are organizing a small social network where each person can be friends with others. You want to represent these friendships in a way that is easy to look up and update.

🎯 Goal: You will build an adjacency list representation of a graph using a JavaScript object. Each key will be a person's name, and the value will be a list of their friends' names.

📋 What You'll Learn

Create a JavaScript object to represent the graph with exact keys and values

Add a variable to hold the name of the person whose friends you want to find

Write code to get the list of friends for that person from the graph

Print the list of friends exactly as an array

💡 Why This Matters

🌍 Real World

Adjacency lists are used to represent networks like social connections, road maps, or computer networks where you want to know which nodes connect to which.

💼 Career

Understanding adjacency lists is important for roles involving graph algorithms, network analysis, and data structure optimization.

1

Create the graph as an adjacency list

Create a JavaScript object called graph with these exact entries: 'Alice': ['Bob', 'Charlie'], 'Bob': ['Alice', 'David'], 'Charlie': ['Alice'], 'David': ['Bob']

DSA Javascript

// Your code here

Hint

Use a JavaScript object with keys as names and values as arrays of friends.

2

Set the person to find friends for

Create a variable called person and set it to the string 'Bob'

DSA Javascript

const graph = {
  'Alice': ['Bob', 'Charlie'],
  'Bob': ['Alice', 'David'],
  'Charlie': ['Alice'],
  'David': ['Bob']
};

// Your code here

Hint

Use const person = 'Bob'; to store the name.

3

Get the list of friends for the person

Create a variable called friends and set it to the value of graph[person]

DSA Javascript

const graph = {
  'Alice': ['Bob', 'Charlie'],
  'Bob': ['Alice', 'David'],
  'Charlie': ['Alice'],
  'David': ['Bob']
};

const person = 'Bob';

// Your code here

Hint

Access the friends list by using bracket notation with the person variable.

4

Print the list of friends

Write a console.log statement to print the variable friends

DSA Javascript

const graph = {
  'Alice': ['Bob', 'Charlie'],
  'Bob': ['Alice', 'David'],
  'Charlie': ['Alice'],
  'David': ['Bob']
};

const person = 'Bob';

const friends = graph[person];

// Your code here

Hint

Use console.log(friends); to display the friends array.

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