Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list for directed weighted graph

What is the printed adjacency list after running this TypeScript code for a directed weighted graph?

DSA Typescript

type Edge = { to: number; weight: number };
const graph: Map<number, Edge[]> = new Map();

function addEdge(from: number, to: number, weight: number) {
  if (!graph.has(from)) graph.set(from, []);
  graph.get(from)!.push({ to, weight });
}

addEdge(1, 2, 5);
addEdge(1, 3, 10);
addEdge(2, 3, 2);
addEdge(3, 1, 7);

for (const [node, edges] of graph.entries()) {
  console.log(`${node} -> ${edges.map(e => `${e.to}(${e.weight})`).join(', ')}`);
}

A 1 -> 2(5), 3(10)\n2 -> 3(2)\n3 -> 1(0)

B 1 -> 2(5), 3(10)\n2 -> 3(2)\n3 -> 1(7)

C 1 -> 2(5)\n2 -> 3(2), 1(7)\n3 -> 3(10)

D 1 -> 3(10)\n2 -> 1(5), 3(2)\n3 -> 1(7)

💡 Hint

Check how edges are added and printed for each node in the directed graph.

The code adds edges from one node to another with weights. It prints each node's edges exactly as added. Option B matches the exact output.

🧠 Conceptual

intermediate

Identify the type of graph from description

Which type of graph is described by: "Edges have no direction and each edge has a number representing cost or distance"?

A Directed Weighted Graph

B Directed Unweighted Graph

C Undirected Weighted Graph

D Undirected Unweighted Graph

💡 Hint

Edges without direction mean connections go both ways.

Edges without direction are undirected. Having a number for cost means weighted. So it is an undirected weighted graph.

🔧 Debug

advanced

Find the error in this undirected graph edge addition

What error will occur when running this TypeScript code to add edges in an undirected graph?

DSA Typescript

const graph: Map<number, number[]> = new Map();

function addEdge(u: number, v: number) {
  if (!graph.has(u)) graph.set(u, []);
  graph.get(u)!.push(v);
  graph.get(v)!.push(u);
}

addEdge(1, 2);
addEdge(2, 3);
console.log(graph);

A TypeError: Cannot read property 'push' of undefined

B No error, graph prints correctly

C ReferenceError: graph is not defined

D SyntaxError: Unexpected token

💡 Hint

Check if both nodes have arrays initialized before pushing.

When adding edge from v to u, graph.get(v) may be undefined if v was not initialized, causing a TypeError.

❓ Predict Output

advanced

Output of BFS traversal on undirected graph

What is the order of nodes printed by this BFS traversal on the undirected graph?

DSA Typescript

const graph: Map<number, number[]> = new Map();

function addEdge(u: number, v: number) {
  if (!graph.has(u)) graph.set(u, []);
  if (!graph.has(v)) graph.set(v, []);
  graph.get(u)!.push(v);
  graph.get(v)!.push(u);
}

addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(3, 5);

function bfs(start: number) {
  const visited = new Set<number>();
  const queue: number[] = [];
  queue.push(start);
  visited.add(start);
  const order: number[] = [];

  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);
    for (const neighbor of graph.get(node)!) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

console.log(bfs(1).join(' -> '));

A 1 -> 2 -> 3 -> 4 -> 5

B 1 -> 3 -> 2 -> 5 -> 4

C 1 -> 2 -> 4 -> 3 -> 5

D 1 -> 3 -> 5 -> 2 -> 4

💡 Hint

BFS visits neighbors level by level in the order they appear in adjacency list.

BFS starts at 1, visits neighbors 2 and 3 in order, then visits neighbors of 2 (4), then neighbors of 3 (5).

🧠 Conceptual

expert

Which graph type allows cycles and weighted edges but no direction?

Select the graph type that can have cycles, edges with weights, and edges without direction.

A Directed Acyclic Weighted Graph

B Undirected Unweighted Graph without cycles

C Directed Weighted Graph without cycles

D Undirected Weighted Graph

💡 Hint

Edges without direction and with weights allow cycles.

Undirected weighted graphs can have cycles and weighted edges without direction.

Practice

1. In a graph, what do we call the points or nodes where edges meet?

easy

A. Edges

B. Weights

C. Vertices

D. Paths

Solution

1. Step 1: Understand graph components

   A graph consists of points called nodes and connections called edges.

2. Step 2: Identify the term for nodes

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option C

4. Quick Check:

   Nodes = Vertices [OK]

Hint: Nodes in graphs are called vertices [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are nodes
• Mixing paths with nodes

2. Which of the following is the correct way to represent a weighted edge from vertex 1 to vertex 2 with weight 5 in TypeScript?

easy

A. const edge = { 1: 2, 5 };

B. const edge = [1, 2, 5];

C. const edge = (1, 2, 5);

D. const edge = { from: 1, to: 2, weight: 5 };

Solution

1. Step 1: Understand object syntax in TypeScript

   Objects use key-value pairs with curly braces and colons.

2. Step 2: Check each option's syntax

   const edge = { from: 1, to: 2, weight: 5 }; correctly uses keys 'from', 'to', and 'weight' with values. const edge = [1, 2, 5]; is an array, valid but less descriptive. const edge = (1, 2, 5); uses parentheses, invalid for object. const edge = { 1: 2, 5 }; has invalid syntax.

3. Final Answer:

   const edge = { from: 1, to: 2, weight: 5 }; -> Option D

4. Quick Check:

   Object with keys and values = const edge = { from: 1, to: 2, weight: 5 }; [OK]

Hint: Use curly braces and key:value pairs for objects [OK]

Common Mistakes:

• Using parentheses instead of braces
• Incorrect object key syntax
• Confusing arrays with objects

3. What will be the output of the following TypeScript code that creates a directed weighted graph and prints its edges?

type Edge = { from: number; to: number; weight: number };
const graph: Edge[] = [
  { from: 1, to: 2, weight: 3 },
  { from: 2, to: 3, weight: 4 },
  { from: 3, to: 1, weight: 5 }
];
for (const edge of graph) {
  console.log(`${edge.from} -> ${edge.to} (weight: ${edge.weight})`);
}

medium

A. 1 -> 2 (weight: 3)
2 -> 3 (weight: 4)
3 -> 1 (weight: 5)

B. 1 -> 2 (weight: 5)
2 -> 3 (weight: 3)
3 -> 1 (weight: 4)

C. 1 -> 3 (weight: 5)
2 -> 1 (weight: 4)
3 -> 2 (weight: 3)

D. Error: Invalid graph definition

Solution

1. Step 1: Read the graph array

   The graph array has edges: 1->2 with weight 3, 2->3 with weight 4, 3->1 with weight 5.

2. Step 2: Trace the for loop output

   The loop prints each edge in the format 'from -> to (weight: weight)'. So output matches 1 -> 2 (weight: 3) 2 -> 3 (weight: 4) 3 -> 1 (weight: 5) exactly.

3. Final Answer:

   1 -> 2 (weight: 3) 2 -> 3 (weight: 4) 3 -> 1 (weight: 5) -> Option A

4. Quick Check:

   Print edges as defined = 1 -> 2 (weight: 3) 2 -> 3 (weight: 4) 3 -> 1 (weight: 5) [OK]

Hint: Match printed edges exactly as in array order [OK]

Common Mistakes:

• Mixing up weights and vertices
• Reversing edge directions
• Assuming syntax error

4. Identify the error in the following TypeScript code that tries to create an undirected weighted graph:

type Edge = { from: number; to: number; weight: number };
const graph: Edge[] = [
  { from: 1, to: 2, weight: 7 },
  { from: 2, to: 1, weight: 7 },
  { from: 2, to: 3, weight: 5 }
];
function addEdge(from: number, to: number, weight: number) {
  graph.push({ from, to, weight });
  graph.push({ from: to, to: from, weight });
}
addEdge(3, 4, 6);
console.log(graph.length);

medium

A. No error; graph length will be 5

B. Error: Duplicate edges cause conflict

C. Error: addEdge function pushes edges incorrectly

D. Error: graph array is immutable

Solution

1. Step 1: Count initial edges

   Initially, graph has 3 edges: 1->2, 2->1, 2->3.

2. Step 2: Analyze addEdge function call

   addEdge(3, 4, 6) pushes { from: 3, to: 4, weight: 6 } and { from: 4, to: 3, weight: 6 }, adding 2 more edges for undirected graph.

3. Step 3: Calculate final length

   3 initial + 2 added = 5. No errors occur; code runs successfully.

4. Final Answer:

   No error; graph length will be 5 -> Option A

5. Quick Check:

   3 + 2 = 5 [OK]

Hint: Count edges before and after addEdge call [OK]

Common Mistakes:

• Assuming duplicate edges cause error
• Miscounting edges after push
• Thinking graph is immutable

5. You have a weighted undirected graph represented as an adjacency list in TypeScript:

const graph: Record = {
  1: [{ node: 2, weight: 4 }, { node: 3, weight: 1 }],
  2: [{ node: 1, weight: 4 }, { node: 3, weight: 2 }, { node: 4, weight: 5 }],
  3: [{ node: 1, weight: 1 }, { node: 2, weight: 2 }, { node: 4, weight: 8 }],
  4: [{ node: 2, weight: 5 }, { node: 3, weight: 8 }]
};

// How to find the total weight of edges connected to vertex 2?

Which code snippet correctly calculates the total weight of edges connected to vertex 2?

hard

A. const total = graph[2].map(edge => edge.weight).length;

B. const total = graph[2].reduce((sum, edge) => sum + edge.weight, 0);

C. const total = graph[2].filter(edge => edge.weight > 0);

D. const total = graph.reduce((sum, edges) => sum + edges.weight, 0);

Solution

1. Step 1: Understand adjacency list structure

   graph[2] is an array of edges connected to vertex 2, each with a weight property.

2. Step 2: Calculate total weight

   Use reduce to sum all edge weights in graph[2]. const total = graph[2].reduce((sum, edge) => sum + edge.weight, 0); correctly sums weights. const total = graph[2].map(edge => edge.weight).length; counts edges, not sum. const total = graph[2].filter(edge => edge.weight > 0); filters edges, no sum. const total = graph.reduce((sum, edges) => sum + edges.weight, 0); tries to reduce graph object, invalid.

3. Final Answer:

   const total = graph[2].reduce((sum, edge) => sum + edge.weight, 0); -> Option B

4. Quick Check:

   Sum weights with reduce = const total = graph[2].reduce((sum, edge) => sum + edge.weight, 0); [OK]

Hint: Use reduce to sum weights in adjacency list [OK]

Common Mistakes:

• Using map length instead of sum
• Filtering without summing
• Reducing wrong data structure