Adjacency List Representation in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the output of the adjacency list after running the following code?

DSA Javascript

class Graph {
  constructor() {
    this.adjList = {};
  }

  addVertex(v) {
    if (!this.adjList[v]) this.adjList[v] = [];
  }

  addEdge(v, w) {
    this.adjList[v].push(w);
    this.adjList[w].push(v);
  }
}

const g = new Graph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addEdge('A', 'B');
g.addEdge('A', 'C');
console.log(g.adjList);

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

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

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

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

💡 Hint

Remember that addEdge adds each vertex to the other's adjacency list.

The addEdge method adds each vertex to the other's list, so 'A' connects to 'B' and 'C', and both 'B' and 'C' connect back to 'A'.

❓ Predict Output

intermediate

Resulting adjacency list after removing a vertex

What is the adjacency list after removing vertex 'B' from the graph below?

DSA Javascript

class Graph {
  constructor() {
    this.adjList = {};
  }

  addVertex(v) {
    if (!this.adjList[v]) this.adjList[v] = [];
  }

  addEdge(v, w) {
    this.adjList[v].push(w);
    this.adjList[w].push(v);
  }

  removeVertex(v) {
    while(this.adjList[v].length) {
      const adjVertex = this.adjList[v].pop();
      this.adjList[adjVertex] = this.adjList[adjVertex].filter(x => x !== v);
    }
    delete this.adjList[v];
  }
}

const g = new Graph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addEdge('A', 'B');
g.addEdge('B', 'C');
g.removeVertex('B');
console.log(g.adjList);

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

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

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

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

💡 Hint

Removing a vertex also removes it from other vertices' adjacency lists.

Removing 'B' deletes it and removes 'B' from 'A' and 'C' adjacency lists, leaving 'A' and 'C' with empty arrays.

🔧 Debug

advanced

Identify the error in adjacency list edge addition

What error does the following code produce when adding an edge?

DSA Javascript

class Graph {
  constructor() {
    this.adjList = {};
  }

  addVertex(v) {
    if (!this.adjList[v]) this.adjList[v] = [];
  }

  addEdge(v, w) {
    this.adjList[v].push(w);
    this.adjList[w].push(v);
  }
}

const g = new Graph();
g.addVertex('A');
g.addEdge('A', 'B');

A TypeError: Cannot read property 'push' of undefined

B ReferenceError: g is not defined

C SyntaxError: Unexpected token '.'

D No error, runs successfully

💡 Hint

Check if both vertices exist before adding edges.

Vertex 'B' was never added, so this.adjList['B'] is undefined, causing a TypeError when calling push.

❓ Predict Output

advanced

Output of adjacency list after directed edge additions

What is the adjacency list after adding directed edges as shown?

DSA Javascript

class DirectedGraph {
  constructor() {
    this.adjList = {};
  }

  addVertex(v) {
    if (!this.adjList[v]) this.adjList[v] = [];
  }

  addEdge(v, w) {
    this.adjList[v].push(w);
  }
}

const g = new DirectedGraph();
g.addVertex('X');
g.addVertex('Y');
g.addVertex('Z');
g.addEdge('X', 'Y');
g.addEdge('Y', 'Z');
console.log(g.adjList);

A {"X": [], "Y": ["Z"], "Z": []}

B {"X": ["Y"], "Y": ["Z"], "Z": ["X"]}

C {"X": ["Y", "Z"], "Y": ["Z"], "Z": []}

D {"X": ["Y"], "Y": ["Z"], "Z": []}

💡 Hint

Directed edges only add one-way connections.

Edges go from 'X' to 'Y' and 'Y' to 'Z', so adjacency lists reflect these one-way links.

🧠 Conceptual

expert

Number of edges in an undirected graph adjacency list

Given an undirected graph represented by an adjacency list where each vertex's list contains its neighbors, how do you calculate the total number of edges?

A Sum the lengths of all adjacency lists and divide by 2

B Sum the lengths of all adjacency lists without division

C Sum the lengths of all adjacency lists and multiply by 2

D Count the number of vertices and subtract 1

💡 Hint

Each edge appears twice in an undirected graph adjacency list.

Each edge is counted twice (once for each vertex), so dividing the total sum by 2 gives the correct edge count.

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