Minimum Spanning Tree Prim's Algorithm in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the key values for all vertices in Prim's algorithm.

DSA C

for (int i = 0; i < V; i++) {
    key[i] = [1];
    mstSet[i] = false;
}

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

A-1

B0

CINT_MAX

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing key values to 0 causes incorrect minimum edge selection.

Using negative values for key can cause logic errors.

We initialize all key values to a very large number (infinity) to ensure any edge weight will be smaller and can update the key.

2fill in blank

medium

Complete the code to find the vertex with the minimum key value not yet included in MST.

DSA C

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == false && key[v] < [1]) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

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

Amin

Bkey[v]

CmstSet[v]

Dmin_index

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing key[v] with key[v] itself instead of min.

Using mstSet[v] in comparison instead of key values.

The variable 'min' holds the smallest key found so far. We compare key[v] with min to find the minimum.

3fill in blank

hard

Fix the error in updating the key and parent arrays after including a vertex in MST.

DSA C

for (int v = 0; v < V; v++) {
    if (graph[u][v] && mstSet[v] == false && graph[u][v] < [1]) {
        parent[v] = u;
        key[v] = graph[u][v];
    }
}

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

Akey[u]

Bparent[v]

Cparent[u]

Dkey[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with key[u] instead of key[v].

Using parent array in the comparison instead of key.

We compare the edge weight graph[u][v] with the current key[v] to update the minimum edge weight for vertex v.

4fill in blank

hard

Fill both blanks to complete the loop that constructs the MST and updates arrays.

DSA C

for (int count = 0; count < V - 1; count++) {
    int u = [1](key, mstSet);
    mstSet[u] = true;
    for (int v = 0; v < V; v++) {
        if (graph[u][v] && mstSet[v] == false && graph[u][v] < [2]) {
            parent[v] = u;
            key[v] = graph[u][v];
        }
    }
}

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

AminKey

Bkey[u]

Ckey[v]

DminIndex

Attempts:

3 left

💡 Hint

Common Mistakes

Using key[u] in the comparison instead of key[v].

Using an undefined function name for the first blank.

The function minKey finds the vertex with the minimum key not in MST. The comparison uses key[v] to update minimum edge weights.

5fill in blank

hard

Fill all three blanks to complete the function that prints the MST edges and their weights.

DSA C

void printMST(int parent[], int graph[V][V]) {
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d \n", [1], [2], [3]);
    }
}

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

Aparent[i]

Bi

Cgraph[i][parent[i]]

Dgraph[parent[i]][i]

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the order of vertices in printf causing wrong edge display.

Using graph[i][parent[i]] for weight which may be incorrect if graph is not symmetric.

The edge is from parent[i] to i. The weight is graph[parent[i]][i]. The printf arguments must match this order.