Adjacency List Representation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the printed adjacency list after executing the following TypeScript code?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v)?.push(w);
    this.adjacencyList.get(w)?.push(v);
  }

  printGraph() {
    this.adjacencyList.forEach((neighbors, vertex) => {
      console.log(`${vertex} -> ${neighbors.join(' -> ')} -> null`);
    });
  }
}

const g = new Graph();
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.printGraph();

A

1 -> 3 -> 2 -> null
2 -> 1 -> null
3 -> 1 -> null

B

1 -> 2 -> 3 -> null
2 -> 3 -> 1 -> null
3 -> 2 -> 1 -> null

C

1 -> 2 -> null
2 -> 1 -> 3 -> null
3 -> 1 -> null

D

1 -> 2 -> 3 -> null
2 -> 1 -> null
3 -> 1 -> null

💡 Hint

Remember edges are added in both directions for an undirected graph.

The graph has vertices 1, 2, and 3. Edges connect 1 with 2 and 3. So, vertex 1's neighbors are 2 and 3. Vertices 2 and 3 each have 1 as their neighbor.

❓ Predict Output

intermediate

Adjacency list after removing a vertex

What is the adjacency list printed after removing vertex 2 from the graph below?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v)?.push(w);
    this.adjacencyList.get(w)?.push(v);
  }

  removeVertex(v: number) {
    this.adjacencyList.delete(v);
    this.adjacencyList.forEach((neighbors) => {
      const index = neighbors.indexOf(v);
      if (index !== -1) {
        neighbors.splice(index, 1);
      }
    });
  }

  printGraph() {
    this.adjacencyList.forEach((neighbors, vertex) => {
      console.log(`${vertex} -> ${neighbors.join(' -> ')} -> null`);
    });
  }
}

const g = new Graph();
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(1, 3);
g.removeVertex(2);
g.printGraph();

A

1 -> 3 -> null
3 -> 1 -> null

B

1 -> 2 -> 3 -> null
3 -> 1 -> 2 -> null

C

1 -> null
3 -> null

D

1 -> 3 -> 2 -> null
3 -> 1 -> null

💡 Hint

Removing a vertex also removes it from neighbors' lists.

Vertex 2 is removed. So, it no longer appears as a vertex or neighbor. Vertices 1 and 3 remain connected.

🔧 Debug

advanced

Identify the error in adjacency list edge addition

What error will the following TypeScript code cause when adding an edge?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v).push(w);
    this.adjacencyList.get(w).push(v);
  }
}

const g = new Graph();
g.addVertex(1);
g.addEdge(1, 2);

A SyntaxError: Unexpected token '.'

B No error, edge added successfully

C TypeError: Cannot read property 'push' of undefined

D ReferenceError: g is not defined

💡 Hint

Check if vertices exist before adding edges.

Vertex 2 was never added, so adjacencyList.get(2) returns undefined. Calling push on undefined causes a TypeError.

🧠 Conceptual

advanced

Memory efficiency of adjacency list vs adjacency matrix

Which statement correctly explains why adjacency lists are more memory efficient than adjacency matrices for sparse graphs?

A Adjacency lists store only existing edges, while adjacency matrices allocate space for all possible edges.

B Adjacency matrices store edges as linked lists, which use more memory than arrays.

C Adjacency lists require a fixed-size 2D array, increasing memory usage.

D Adjacency matrices compress edges, making them less memory efficient.

💡 Hint

Think about how each structure stores edges.

Adjacency lists keep only neighbors for each vertex, so they use memory proportional to edges. Adjacency matrices allocate space for all vertex pairs, even if no edge exists.

🚀 Application

expert

Resulting adjacency list after multiple operations

After running the following TypeScript code, what is the printed adjacency list?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v)?.push(w);
    this.adjacencyList.get(w)?.push(v);
  }

  removeEdge(v: number, w: number) {
    this.adjacencyList.set(v, this.adjacencyList.get(v)?.filter(x => x !== w) || []);
    this.adjacencyList.set(w, this.adjacencyList.get(w)?.filter(x => x !== v) || []);
  }

  printGraph() {
    this.adjacencyList.forEach((neighbors, vertex) => {
      console.log(`${vertex} -> ${neighbors.join(' -> ')} -> null`);
    });
  }
}

const g = new Graph();
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addVertex(4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.removeEdge(1, 3);
g.printGraph();

A

1 -> 2 -> 3 -> null
2 -> 1 -> 4 -> null
3 -> 4 -> 1 -> null
4 -> 2 -> 3 -> null

B

1 -> 2 -> null
2 -> 1 -> 4 -> null
3 -> 4 -> null
4 -> 2 -> 3 -> null

C

1 -> 3 -> null
2 -> 4 -> null
3 -> 1 -> 4 -> null
4 -> 2 -> 3 -> null

D

1 -> 2 -> null
2 -> 4 -> null
3 -> 4 -> null
4 -> 2 -> 3 -> null

💡 Hint

Removing edge (1,3) removes 3 from 1's list and 1 from 3's list.

Edges added: (1,2), (1,3), (2,4), (3,4). Then edge (1,3) is removed. So 1's neighbors are only 2, 3's neighbors no longer include 1.