Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Typescript - Execution Trace

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Vertices: Points/Nodes

↓

Edges: Connections

↓

Directed?

Yes→Edges have direction

↓

Undirected: Edges bidirectional

↓

Weighted?

Yes→Edges have weights (costs)

No↓

Edges unweighted

This flow shows how a graph is built from vertices and edges, then edges can be directed or undirected, and weighted or unweighted.

Execution Sample

DSA Typescript

const vertices = ['A', 'B', 'C'];
const edges = [
  { from: 'A', to: 'B', weight: 5 },
  { from: 'B', to: 'C', weight: 3 }
];

Defines a graph with 3 vertices and 2 directed weighted edges.

Execution Table

Step	Operation	Vertices	Edges	Edge Type	Weighted	Visual State
1	Initialize vertices	['A', 'B', 'C']	[]	N/A	N/A	Vertices: A, B, C; No edges yet
2	Add edge from A to B with weight 5	['A', 'B', 'C']	[A -> B (5)]	Directed	Yes	A --5--> B; C isolated
3	Add edge from B to C with weight 3	['A', 'B', 'C']	[A -> B (5), B -> C (3)]	Directed	Yes	A --5--> B --3--> C
4	Check if edges are directed	['A', 'B', 'C']	[A -> B (5), B -> C (3)]	Directed	Yes	Edges have direction from source to target
5	Check if edges are weighted	['A', 'B', 'C']	[A -> B (5), B -> C (3)]	Directed	Yes	Edges carry weights 5 and 3
6	End of graph definition	['A', 'B', 'C']	[A -> B (5), B -> C (3)]	Directed	Yes	Graph fully defined

💡 All vertices and edges added; graph is directed and weighted

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
vertices	[]	['A', 'B', 'C']	['A', 'B', 'C']	['A', 'B', 'C']
edges	[]	[A -> B (5)]	[A -> B (5), B -> C (3)]	[A -> B (5), B -> C (3)]
edgeType	N/A	Directed	Directed	Directed
weighted	N/A	Yes	Yes	Yes

Key Moments - 3 Insights

Why do we say edges are 'directed' or 'undirected'?

Because directed edges have a clear start and end point (like one-way streets), while undirected edges connect two vertices both ways (like two-way streets). See execution_table rows 2 and 4 where edges are added and identified as directed.

What does it mean for edges to be weighted?

Weighted edges carry a number (weight) that can represent cost, distance, or capacity. In the table rows 2 and 3, each edge has a weight (5 and 3), showing weighted edges.

Can a graph have both directed and undirected edges?

Usually a graph is either directed or undirected for consistency. Mixing them is possible but uncommon and complicates traversal. Our example in rows 4 and 5 shows a directed graph.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, how many edges does the graph have?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Edges' column at step 3 in execution_table

At which step do we confirm the edges are weighted?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Weighted' column in execution_table rows

If edges were undirected, how would the visual state change at step 3?

A Edges would have arrows both ways between vertices

B Edges would disappear

C Vertices would be removed

D Weights would be ignored

💡 Hint

Refer to concept_flow where directed edges have one arrow, undirected have two-way connection

Concept Snapshot

Graph = vertices (points) + edges (connections)
Edges can be directed (one-way) or undirected (two-way)
Edges can be weighted (carry a number) or unweighted
Directed edges show direction from source to target
Weighted edges represent cost, distance, or capacity

Full Transcript

A graph consists of vertices, which are points or nodes, and edges, which connect these vertices. Edges can be directed, meaning they go from one vertex to another in a specific direction, or undirected, meaning the connection goes both ways. Additionally, edges can be weighted, carrying a number that represents cost or distance, or unweighted, meaning no such number is attached. In the example, we defined three vertices A, B, and C, and added two directed weighted edges: from A to B with weight 5, and from B to C with weight 3. This setup helps understand basic graph terminology and structure.

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