Minimum spanning tree (Kruskal's) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to select the next edge with the smallest weight in Kruskal's algorithm.

Data Structures Theory

edges.sort(key=lambda edge: edge.[1])

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

Aweight

Bcost

Clength

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'length' or 'cost' instead of 'weight' which is the standard term.

Trying to sort by 'value' which is not a property of edges.

In Kruskal's algorithm, edges are sorted by their weight to pick the smallest edge first.

2fill in blank

medium

Complete the code to check if adding an edge creates a cycle using the union-find data structure.

Data Structures Theory

if find(parent, u) != [1](parent, v):

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

Amerge

Bunion

Cconnect

Dfind

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'union' instead of 'find' to check parents.

Using unrelated functions like 'connect' or 'merge'.

To check if two vertices belong to different sets, we use the find function on both.

3fill in blank

hard

Fix the error in the union operation to correctly merge two sets in Kruskal's algorithm.

Data Structures Theory

def union(parent, rank, u, v):
    root_u = find(parent, u)
    root_v = find(parent, v)
    if root_u != root_v:
        if rank[root_u] < rank[root_v]:
            parent[root_u] = [1]
        else:
            parent[root_v] = root_u
            if rank[root_u] == rank[root_v]:
                rank[root_u] += 1

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

Au

Broot_u

Croot_v

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[root_u] = root_u which causes a cycle.

Using the original vertices u or v instead of their roots.

When the rank of root_u is less, we attach root_u's parent to root_v to keep the tree shallow.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each vertex to its parent after union-find operations.

Data Structures Theory

parent_map = {vertex: [1](parent, vertex) for vertex in [2]

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

Afind

Bvertices

Cnodes

Dget_parent

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'get_parent' which is not a standard function.

Using 'nodes' instead of the variable that holds all vertices.

The dictionary maps each vertex in the set vertices to its root parent found by the find function.

5fill in blank

hard

Fill all three blanks to complete the Kruskal's algorithm loop that adds edges to the MST.

Data Structures Theory

for edge in [1]:
    u, v, weight = edge
    if find(parent, u) != find(parent, v):
        [2](parent, rank, u, v)
        mst_edges.append([3])

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

Aedges

Bunion

Cedge

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'graph' instead of 'edges' to iterate.

Appending 'u' or 'v' instead of the whole edge.

The loop goes through all edges, uses union to merge sets, and adds the current edge to the MST list.