Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Python - Build from Scratch

Graph Terminology: Vertices, Edges, Directed, Undirected, Weighted

📖 Scenario: You are helping a city planner represent a small map of locations and roads between them. Each location is a vertex, and each road is an edge. Some roads have directions (one-way), and some have distances (weights).

🎯 Goal: You will create a graph using a dictionary where keys are locations (vertices) and values are lists of connected locations with distances. You will mark if roads are one-way (directed) or two-way (undirected), and include distances (weights) for each road.

📋 What You'll Learn

Create a dictionary called city_map with exact vertices and edges

Add a boolean variable is_directed to indicate if the graph is directed

Use a loop to create a list of all edges with their weights

Print the list of edges showing connections and distances

💡 Why This Matters

🌍 Real World

City planners and map applications use graphs to represent locations and roads, including one-way streets and distances.

💼 Career

Understanding graph representations is essential for software engineers working on navigation, network routing, and data modeling.

1

Create the graph dictionary with vertices and weighted edges

Create a dictionary called city_map with these exact entries: 'A': [('B', 5), ('C', 10)], 'B': [('C', 3)], 'C': [('A', 2)]

DSA Python

# Create the city_map dictionary with vertices and weighted edges
# Your code here

Hint

Think of city_map as a dictionary where each key is a location and the value is a list of tuples. Each tuple has a connected location and the distance.

2

Add a variable to indicate if the graph is directed

Create a boolean variable called is_directed and set it to True because roads are one-way

DSA Python

city_map = {
    'A': [('B', 5), ('C', 10)],
    'B': [('C', 3)],
    'C': [('A', 2)]
}
# Create is_directed variable and set it to True
# Your code here

Hint

Since roads are one-way, is_directed should be True.

3

Create a list of all edges with weights using a loop

Create an empty list called edges. Use a for loop with variables start and connections to iterate over city_map.items(). Inside, use another for loop with variables end and weight to iterate over connections. Append tuples (start, end, weight) to edges

DSA Python

city_map = {
    'A': [('B', 5), ('C', 10)],
    'B': [('C', 3)],
    'C': [('A', 2)]
}
is_directed = True

# Create edges list and fill it with tuples (start, end, weight)
# Your code here

Hint

Use nested loops: outer loop over city_map.items(), inner loop over each connections list.

4

Print the list of edges with their weights

Use print(edges) to display the list of edges with their weights

DSA Python

city_map = {
    'A': [('B', 5), ('C', 10)],
    'B': [('C', 3)],
    'C': [('A', 2)]
}
is_directed = True

edges = []
for start, connections in city_map.items():
    for end, weight in connections:
        edges.append((start, end, weight))

# Print the edges list
# Your code here

Hint

The output should be a list of tuples showing each edge with its start, end, and weight.

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