Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a list of all vertices in the graph.

DSA Python

vertices = [[1] for edge in edges for vertex in edge]

Drag options to blanks, or click blank then click option'

Aedge

Bvertex

Cvertices

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'edge' instead of 'vertex' collects pairs, not single nodes.

Using 'vertices' or 'graph' which are not defined in this context.

The variable vertex represents each node in the edges, so we collect all vertices by iterating over edges and then over each vertex in those edges.

2fill in blank

medium

Complete the code to check if the graph is directed by comparing edges.

DSA Python

is_directed = any((v2, v1) not in edges for (v1, v2) in edges if v1 != v2 and [1])

Drag options to blanks, or click blank then click option'

Av1 != v2

Bv2 != v1

Cv1 == v2

Dv2 == v1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'v2 != v1' which is the same as 'v1 != v2' but less clear.

Using equality checks that include self-loops.

We check only edges where the two vertices are different to avoid self-loops affecting the directed check.

3fill in blank

hard

Fix the error in the code to correctly add weighted edges to the graph dictionary.

DSA Python

graph = {}
for (u, v, w) in weighted_edges:
    if u not in graph:
        graph[u] = []
    graph[u].[1]((v, w))

Drag options to blanks, or click blank then click option'

Ainsert

Badd

Cappend

Dextend

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'add' which is for sets, not lists.

Using 'extend' which expects an iterable and would add each element separately.

We use append to add a tuple (v, w) to the adjacency list for vertex u.

4fill in blank

hard

Fill both blanks to create a dictionary of vertices with their degrees in an undirected graph.

DSA Python

degree = {vertex: 0 for vertex in vertices}
for (u, v) in edges:
    degree[[1]] += 1
    degree[[2]] += 1

Drag options to blanks, or click blank then click option'

Au

Bv

Cvertex

Dedges

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'vertex' or 'edges' which are not the variables for the edge ends.

Increasing degree for only one vertex instead of both.

In an undirected graph, each edge increases the degree of both vertices u and v by 1.

5fill in blank

hard

Fill all three blanks to create a weighted adjacency dictionary from a list of edges.

DSA Python

weighted_graph = {}
for (src, dest, weight) in weighted_edges:
    if [1] not in weighted_graph:
        weighted_graph[[2]] = []
    weighted_graph[src].append(([3], weight))

Drag options to blanks, or click blank then click option'

Asrc

Bdest

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up source and destination keys.

Appending the wrong vertex or weight.

We check if src is in the dictionary, add it if missing, then append the tuple (dest, weight) to the adjacency list for src.

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