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

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Identify Vertices

↓

Identify Edges

↓

Check Edge Type

↓

Directed

↓

Check Weight

↓

Weighted

↓

Graph Type Defined

The flow shows how a graph is defined by vertices and edges, then edges are classified as directed or undirected, and further as weighted or unweighted.

Execution Sample

DSA Python

graph = {
  'A': [('B', 3), ('C', 5)],
  'B': [('C', 2)],
  'C': []
}

Defines a weighted directed graph with vertices A, B, C and edges with weights.

Execution Table

Step	Operation	Vertices	Edges	Edge Type	Weighted?	Visual State
1	Define vertices	A, B, C	None yet	N/A	N/A	Vertices: A, B, C
2	Add edge A->B with weight 3	A, B, C	A->B	Directed	Yes	A -> B (3)
3	Add edge A->C with weight 5	A, B, C	A->B, A->C	Directed	Yes	A -> B (3), A -> C (5)
4	Add edge B->C with weight 2	A, B, C	A->B, A->C, B->C	Directed	Yes	A -> B (3), A -> C (5), B -> C (2)
5	No edges from C	A, B, C	A->B, A->C, B->C	Directed	Yes	A -> B (3), A -> C (5), B -> C (2)
6	Graph fully defined	A, B, C	A->B, A->C, B->C	Directed	Yes	Complete weighted directed graph

💡 All vertices and edges defined with direction and weights, graph construction complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Vertices	None	['A', 'B', 'C']	['A', 'B', 'C']	['A', 'B', 'C']	['A', 'B', 'C']	['A', 'B', 'C']
Edges	None	[]	[('A', 'B', 3)]	[('A', 'B', 3), ('A', 'C', 5)]	[('A', 'B', 3), ('A', 'C', 5), ('B', 'C', 2)]	[('A', 'B', 3), ('A', 'C', 5), ('B', 'C', 2)]
Edge Type	N/A	N/A	Directed	Directed	Directed	Directed
Weighted	N/A	N/A	Yes	Yes	Yes	Yes

Key Moments - 3 Insights

Why do edges have direction in a directed graph?

Edges have direction to show the path goes from one vertex to another specifically, as seen in steps 2-4 where edges are A->B, A->C, B->C, not the reverse.

What does it mean for an edge to be weighted?

Weighted edges carry a value (weight) representing cost or distance, shown in the visual state with numbers like (3), (5), (2) in steps 2-4.

Can a graph have edges without weights?

Yes, if edges have no associated numbers, they are unweighted. This example uses weights, but unweighted graphs omit these values.

Visual Quiz - 3 Questions

Look at the execution table at step 3, which edges exist?

A A->B only

B B->C only

C A->B and A->C

D No edges yet

💡 Hint

Check the 'Edges' column in row for step 3 in execution_table.

At which step does the graph first become weighted?

A Step 2

B Step 1

C Step 4

D Step 5

💡 Hint

Look at the 'Weighted?' column in execution_table rows.

If edges had no weights, how would the 'Weighted?' column change?

A It would be empty

B It would say 'No' for all steps

C It would say 'Yes' for all steps

D It would say 'N/A' only at step 1

💡 Hint

Weighted means edges have numbers; no weights means 'No' in that column.

Concept Snapshot

Graph = vertices + edges
Edges connect vertices
Edges can be directed or undirected
Edges can be weighted or unweighted
Directed edges have arrows showing direction
Weighted edges have values showing cost or distance

Full Transcript

A graph is made of points called vertices and connections called edges. Edges can have direction, meaning they go from one vertex to another specifically, or be undirected, meaning they connect both ways. Edges can also have weights, which are numbers representing cost or distance. This example shows a weighted directed graph with vertices A, B, C and edges like A to B with weight 3. The execution table tracks adding vertices and edges step-by-step, showing how the graph builds up. Key points include understanding direction means one-way connection and weights add extra information to edges. The visual quiz tests understanding of edges present at each step, when weights appear, and what changes if weights are removed.

Practice

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

easy

A. Vertices

B. Edges

C. Weights

D. Paths

Solution

1. Step 1: Understand graph components

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

2. Step 2: Identify the term for points

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option A

4. Quick Check:

   Points in graph = Vertices [OK]

Hint: Vertices are the points, edges are the lines connecting them [OK]

Common Mistakes:

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

2. Which of the following is the correct way to represent a weighted edge from vertex A to vertex B with weight 5 in Python using a tuple?

easy

A. (5, A, B)

B. [A, B, 5]

C. {'A': 'B', 'weight': 5}

D. (A, B, 5)

Solution

1. Step 1: Understand tuple representation

   A weighted edge is often represented as a tuple (start_vertex, end_vertex, weight).

2. Step 2: Match the correct tuple format

   The tuple (A, B, 5) correctly shows an edge from A to B with weight 5.

3. Final Answer:

   (A, B, 5) -> Option D

4. Quick Check:

   Weighted edge tuple = (start, end, weight) [OK]

Hint: Weighted edges use (start, end, weight) tuple format [OK]

Common Mistakes:

• Using list instead of tuple
• Putting weight first
• Using dictionary instead of tuple

3. What will be the output of the following Python code snippet?

graph = { 'A': ['B', 'C'], 'B': ['C'], 'C': ['A'] }
print(len(graph['A']))

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Analyze the graph dictionary

   Key 'A' has a list of neighbors ['B', 'C'], so graph['A'] is ['B', 'C'].

2. Step 2: Calculate length of neighbors list

   len(graph['A']) counts the number of neighbors, which is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Neighbors of A = 2 [OK]

Hint: Count neighbors in adjacency list for vertex [OK]

Common Mistakes:

• Counting total keys instead of neighbors
• Confusing keys with values
• Off-by-one counting errors

4. Identify the error in the following Python code that tries to create an undirected graph using adjacency lists:

graph = { 'A': ['B'], 'B': ['C'], 'C': [] }
graph['C'].append('A')

medium

A. The code is correct for undirected graph

B. Appending 'A' to 'C' creates a cycle

C. The graph is directed, not undirected

D. Missing edge from 'B' to 'A'

Solution

1. Step 1: Understand undirected graph representation

   In an undirected graph, edges go both ways, so adjacency lists must be symmetric.

2. Step 2: Check the adjacency lists

   Initially, 'A' connects to 'B', but 'B' does not connect back to 'A', so it's directed.

3. Final Answer:

   The graph is directed, not undirected -> Option C

4. Quick Check:

   Undirected graph needs two-way edges [OK]

Hint: Undirected graphs have symmetric edges in adjacency lists [OK]

Common Mistakes:

• Assuming one-way edges are undirected
• Ignoring symmetry in adjacency lists
• Confusing cycles with direction

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

graph = {
  'A': [('B', 3), ('C', 5)],
  'B': [('A', 3), ('C', 1)],
  'C': [('A', 5), ('B', 1)]
}

What is the total weight of all edges in this graph?

hard

A. 18

B. 9

C. 6

D. 3

Solution

1. Step 1: List all edges with weights

   Edges: A-B(3), A-C(5), B-C(1). Each edge appears twice because graph is undirected.

2. Step 2: Sum weights and divide by 2

   Total sum counting duplicates = 3+5+3+1+5+1 = 18. Divide by 2 to avoid double counting: 18 / 2 = 9.

3. Final Answer:

   9 -> Option B

4. Quick Check:

   Sum weights once for undirected edges [OK]

Hint: Sum all weights then halve for undirected graphs [OK]

Common Mistakes:

• Counting edges twice
• Forgetting to divide by 2
• Ignoring weights in tuples