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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list for an undirected weighted graph

What is the printed adjacency list after running this code for an undirected weighted graph?

DSA Python

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

for vertex, edges in graph.items():
    print(f"{vertex} -> {edges}")

A A -> [('B', 3)]\nB -> [('A', 3), ('C', 1)]\nC -> [('A', 5)]

B A -> [('B', 3), ('C', 5)]\nB -> [('C', 1)]\nC -> [('A', 5), ('B', 1)]

C A -> [('B', 3), ('C', 5)]\nB -> [('A', 3), ('C', 1)]\nC -> [('A', 5), ('B', 1)]

D A -> [('B', 3), ('C', 5)]\nB -> [('A', 3), ('C', 1)]\nC -> [('B', 1)]

💡 Hint

Remember that in an undirected graph, edges appear in both connected vertices' lists.

In an undirected weighted graph, each edge is stored twice: once for each vertex it connects, with the same weight.

❓ Predict Output

intermediate

Output of adjacency list for a directed graph

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

DSA Python

graph = {
    'X': ['Y', 'Z'],
    'Y': ['Z'],
    'Z': []
}

for vertex, edges in graph.items():
    print(f"{vertex} -> {edges}")

A X -> ['Z']\nY -> ['Z']\nZ -> []

B X -> ['Y']\nY -> ['Z']\nZ -> ['X']

C X -> ['Y', 'Z']\nY -> ['X']\nZ -> []

D X -> ['Y', 'Z']\nY -> ['Z']\nZ -> []

💡 Hint

In a directed graph, edges go only one way from source to destination.

The adjacency list for a directed graph shows edges only from the source vertex to its neighbors, not the other way around.

🧠 Conceptual

advanced

Identify the type of graph from description

Which type of graph is described by: "Edges have directions and weights, and edges only go one way from one vertex to another"?

A Undirected weighted graph

B Directed weighted graph

C Undirected unweighted graph

D Directed unweighted graph

💡 Hint

Edges have direction and weights, so both properties matter.

A graph with edges that have direction and weights is called a directed weighted graph.

🔧 Debug

advanced

Find the error in this graph representation

What error will this code cause when representing an undirected graph?

DSA Python

graph = {
    'P': ['Q'],
    'Q': []
}

# Adding edge from Q to P missing

for vertex, edges in graph.items():
    print(f"{vertex} -> {edges}")

A No error, but the graph is incomplete for undirected edges

B KeyError because 'P' is missing in 'Q' edges

C SyntaxError due to missing colon

D TypeError because edges is not iterable

💡 Hint

Check if edges appear in both vertices for undirected graphs.

The code runs fine but misses the edge from 'Q' to 'P', so the undirected edge is incomplete.

🚀 Application

expert

Number of edges in a weighted undirected graph

Given this weighted undirected graph adjacency list, how many unique edges does it have?

DSA Python

graph = {
    'M': [('N', 2), ('O', 4)],
    'N': [('M', 2), ('O', 3)],
    'O': [('M', 4), ('N', 3)]
}

A 3

B 6

C 4

D 2

💡 Hint

Count each edge only once since the graph is undirected.

Each edge appears twice in the adjacency list, once for each vertex. Counting unique edges gives 3.

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