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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the in-degree list with zeros for all vertices.

DSA Python

in_degree = [[1] for _ in range(num_vertices)]

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

A0

B1

CNone

Dnum_vertices

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 initializes in-degree incorrectly.

Using None causes errors when incrementing.

We start with zero in-degree for all vertices before counting incoming edges.

2fill in blank

medium

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

DSA Python

for vertex in range(num_vertices):
    if in_degree[vertex] == [1]:
        queue.append(vertex)

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

A-1

B1

C0

Dnum_vertices

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 1 instead of 0 misses correct vertices.

Using negative values causes logic errors.

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

3fill in blank

hard

Fix the error in the code to correctly decrement the in-degree of adjacent vertices.

DSA Python

for neighbor in graph[vertex]:
    in_degree[neighbor] [1] 1
    if in_degree[neighbor] == 0:
        queue.append(neighbor)

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

A+=

B/=

C*=

D-=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+=' increases in-degree incorrectly.

Using '*=' or '/=' causes wrong calculations.

We reduce the in-degree by 1 when removing an edge from the graph.

4fill in blank

hard

Fill both blanks to complete the while loop that processes vertices in the queue.

DSA Python

while queue:
    vertex = queue.[1]()
    topo_order.[2](vertex)

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

Apop

Bappend

Cpop(0)

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() removes from the end, not the front.

Using insert instead of append changes the order.

We remove the first vertex from the queue using pop(0) and add it to the topological order with append.

5fill in blank

hard

Fill all three blanks to complete the function that returns the topological order or empty list if cycle detected.

DSA Python

def kahn_topological_sort(graph, num_vertices):
    in_degree = [0 for _ in range(num_vertices)]
    for vertex in range(num_vertices):
        for neighbor in graph[vertex]:
            in_degree[neighbor] [1] 1
    queue = [v for v in range(num_vertices) if in_degree[v] == 0]
    topo_order = []
    while queue:
        vertex = queue.[2]()
        topo_order.[3](vertex)
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    if len(topo_order) == num_vertices:
        return topo_order
    else:
        return []

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

A+=

Bpop(0)

Cappend

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-=' instead of '+=' when counting in-degree.

Using pop() instead of pop(0) changes processing order.

Using insert instead of append changes output order.

Increment in-degree by 1 for each neighbor, pop from front of queue, and append to topo_order.

Practice

1. What is the main purpose of Kahn's Algorithm in graph theory?

easy

A. To find a topological ordering of a Directed Acyclic Graph (DAG)

B. To detect cycles in an undirected graph

C. To find the shortest path between two nodes

D. To calculate the minimum spanning tree

Solution

1. Step 1: Understand Kahn's Algorithm goal

   Kahn's Algorithm is designed to produce a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, u comes before v in the ordering.

2. Step 2: Compare with other graph algorithms

   Other options describe different algorithms: cycle detection, shortest path, and minimum spanning tree are unrelated to Kahn's Algorithm.

3. Final Answer:

   To find a topological ordering of a Directed Acyclic Graph (DAG) -> Option A

4. Quick Check:

   Topological sort = Kahn's Algorithm purpose [OK]

Hint: Kahn's Algorithm always finds order in DAGs [OK]

Common Mistakes:

• Confusing topological sort with cycle detection
• Thinking it works on undirected graphs
• Mixing it up with shortest path algorithms

2. Which of the following Python code snippets correctly initializes the in-degree array for Kahn's Algorithm given a graph adjacency list graph with n nodes?

easy

A. in_degree = [0] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1

B. in_degree = [0] * n
for v in range(n):
for u in graph[v]:
in_degree[v] += 1

C. in_degree = [1] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1

D. in_degree = [0] * n
for u in graph:
for v in graph[u]:
in_degree[u] += 1

Solution

1. Step 1: Understand in-degree calculation

   In-degree of a node is the count of edges coming into it. For each edge u -> v, increment in_degree[v].

2. Step 2: Analyze code snippets

   in_degree = [0] * n for u in range(n): for v in graph[u]: in_degree[v] += 1 correctly loops over each node u and its neighbors v, incrementing in_degree[v]. in_degree = [0] * n for v in range(n): for u in graph[v]: in_degree[v] += 1 increments the source node incorrectly. in_degree = [1] * n for u in range(n): for v in graph[u]: in_degree[v] += 1 initializes in_degree with 1s, which is wrong. in_degree = [0] * n for u in graph: for v in graph[u]: in_degree[u] += 1 increments in_degree[u], which is incorrect.

3. Final Answer:

   in_degree = [0] * n for u in range(n): for v in graph[u]: in_degree[v] += 1 -> Option A

4. Quick Check:

   Increment in_degree of destination node [OK]

Hint: Increment in-degree of target nodes, not source [OK]

Common Mistakes:

• Incrementing in-degree of source node instead of target
• Initializing in-degree with wrong default values
• Swapping loop variables u and v

3. What is the output of the following Python code implementing Kahn's Algorithm on the graph with edges: 0->1, 0->2, 1->3, 2->3?

from collections import deque

graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
n = 4
in_degree = [0]*n
for u in range(n):
    for v in graph[u]:
        in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
topo_order = []
while queue:
    node = queue.popleft()
    topo_order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)
print(topo_order)

medium

A. [0, 1, 2, 3]

B. [3, 1, 2, 0]

C. [0, 2, 1, 3]

D. [1, 2, 0, 3]

Solution

1. Step 1: Calculate in-degree and initialize queue

   In-degree: 0=0, 1=1, 2=1, 3=2. Queue starts with nodes having in-degree 0: [0].

2. Step 2: Process nodes in queue

   Pop 0, append to topo_order: [0]. Decrement in-degree of 1 and 2 to 0, add both to queue: [1, 2]. Pop 1, append: [0,1]. Decrement in-degree of 3 to 1. Pop 2, append: [0,1,2]. Decrement in-degree of 3 to 0, add 3 to queue: [3]. Pop 3, append: [0,1,2,3].

3. Final Answer:

   [0, 2, 1, 3] -> Option C

4. Quick Check:

   Topological order = [0, 2, 1, 3] [OK]

Hint: Start with zero in-degree nodes, process neighbors reducing in-degree [OK]

Common Mistakes:

• Ignoring order of nodes with zero in-degree
• Not updating in-degree after popping nodes
• Appending nodes before in-degree reaches zero

4. Identify the error in the following Kahn's Algorithm code snippet and choose the correct fix:

from collections import deque

graph = {0: [1], 1: [2], 2: [0]}
n = 3
in_degree = [0]*n
for u in range(n):
    for v in graph[u]:
        in_degree[u] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
topo_order = []
while queue:
    node = queue.popleft()
    topo_order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)
print(topo_order)

medium

A. Initialize in_degree with ones instead of zeros

B. Change 'in_degree[u] += 1' to 'in_degree[v] += 1' to correctly count incoming edges

C. Replace deque with list for queue implementation

D. Remove the while loop to avoid infinite processing

Solution

1. Step 1: Identify incorrect in-degree update

   The code increments in_degree[u] for edges u->v, but it should increment in_degree[v] because in-degree counts incoming edges to v.

2. Step 2: Understand impact on queue initialization

   Incorrect in-degree causes wrong zero in-degree nodes, so queue may be empty or incorrect, breaking the algorithm.

3. Final Answer:

   Change 'in_degree[u] += 1' to 'in_degree[v] += 1' to correctly count incoming edges -> Option B

4. Quick Check:

   Increment in-degree of target node, not source [OK]

Hint: In-degree counts edges coming into a node, increment target node [OK]

Common Mistakes:

• Incrementing in-degree of source node
• Not detecting cycles due to wrong in-degree
• Using wrong data structure for queue

5. Given a Directed Acyclic Graph (DAG) with nodes 0 to 5 and edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1, which of the following is a valid topological order produced by Kahn's Algorithm?

hard

A. [4, 5, 2, 3, 1, 0]

B. [5, 4, 2, 3, 1, 0]

C. [0, 1, 2, 3, 4, 5]

D. [4, 5, 0, 2, 3, 1]

Solution

1. Step 1: Calculate in-degree for each node

   In-degree: 0=2 (from 5,4), 1=2 (from 4,3), 2=1 (from 5), 3=1 (from 2), 4=0, 5=0. Start queue with nodes 4 and 5.

2. Step 2: Process nodes in queue and build order

   Pop 4: order=[4], decrement in-degree of 0 to 1 and 1 to 1. Pop 5: order=[4,5], assuming graph[5]=[0,2], decrement 0 to 0 and append 0, decrement 2 to 0 and append 2: queue=[0,2]. Pop 0: order=[4,5,0]. Pop 2: order=[4,5,0,2], decrement 3 to 0, append 3. Pop 3: order=[4,5,0,2,3], decrement 1 to 0, append 1. Pop 1: order=[4,5,0,2,3,1].

3. Final Answer:

   [4, 5, 0, 2, 3, 1] -> Option D

4. Quick Check:

   Valid topological order respects edges [OK]

Hint: Start with zero in-degree nodes, remove edges, add new zero in-degree nodes [OK]

Common Mistakes:

• Ignoring in-degree counts leading to invalid order
• Placing nodes before their dependencies
• Assuming any order is valid without checking edges