Topological Sort Using Kahn's Algorithm BFS in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the in-degree array to zero for all vertices.

DSA C

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

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

A0

BV

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting in-degree to 1 initially

Using negative values for in-degree

In-degree counts the number of incoming edges. Initially, it should be zero for all vertices.

2fill in blank

medium

Complete the code to enqueue vertices with zero in-degree into the queue.

DSA C

for (int i = 0; i < V; i++) {
    if (in_degree[i] == [1]) {
        enqueue(&q, i);
    }
}

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

AV

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Enqueuing vertices with in-degree 1

Forgetting to check in-degree

Vertices with zero in-degree have no dependencies and can be processed first.

3fill in blank

hard

Fix the error in the code that decreases the in-degree of adjacent vertices after removing a vertex from the queue.

DSA C

while (!is_empty(&q)) {
    int u = dequeue(&q);
    for (int i = 0; i < adj[u].size; i++) {
        int v = adj[u].array[i];
        in_degree[v] [1] 1;
        if (in_degree[v] == 0) {
            enqueue(&q, v);
        }
    }
}

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

A*=

B-=

C+=

D/=

Attempts:

3 left

💡 Hint

Common Mistakes

Increasing in-degree instead of decreasing

Using multiplication or division operators

When a vertex is removed, the in-degree of its adjacent vertices decreases by one.

4fill in blank

hard

Fill both blanks to correctly update the topological order array and its index.

DSA C

topo_order[[1]] = u;
[2]++;

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

Aindex

Bcount

Ci

Dpos

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for assignment and increment

Forgetting to increment the index

The variable 'index' tracks the position in the topological order array and should be incremented after assignment.

5fill in blank

hard

Fill all three blanks to complete the condition that checks if a cycle exists in the graph.

DSA C

if ([1] != [2]) {
    printf("Cycle detected, topological sort not possible.\n");
    return [3];
}

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

Acount

BV

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of -1

Comparing wrong variables

If the number of vertices processed is not equal to total vertices, a cycle exists. Returning -1 indicates failure.