BFS traversal and applications in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue for BFS traversal.

Data Structures Theory

queue = [[1]]

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

Agraph

Bvisited

Cstart_node

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Starting the queue with an empty list or None.

Using the visited set instead of the start node.

In BFS, the queue starts with the starting node to begin traversal.

2fill in blank

medium

Complete the code to mark a node as visited during BFS.

Data Structures Theory

visited.add([1])

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

Agraph

Bneighbor

Cqueue

Dcurrent_node

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the entire graph or queue to visited.

Adding neighbors before checking if they are visited.

We mark the current node as visited to avoid revisiting it.

3fill in blank

hard

Fix the error in the BFS neighbor check condition.

Data Structures Theory

if neighbor not in [1]:

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

Avisited

Bgraph

Cqueue

Dstart_node

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if neighbor is not in the graph or queue instead of visited.

Forgetting to check if neighbor is visited.

We only add neighbors to the queue if they have not been visited yet.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps nodes to their distances from the start node using BFS.

Data Structures Theory

distances = {node: [1] for node in graph if node [2] visited}

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

A0

Bin

Cnot in

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'in' instead of 'not in' in the condition.

Assigning distance 0 to all nodes regardless of visitation.

We assign a default distance of 1 to nodes not yet visited.

The condition checks nodes not in visited.

5fill in blank

hard

Fill all three blanks to complete the BFS function that returns the shortest path length from start to goal.

Data Structures Theory

def bfs_shortest_path(graph, start, goal):
    queue = [(start, 0)]
    visited = set([start])
    while queue:
        current, depth = queue.pop(0)
        if current == goal:
            return [1]
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, [2]))
    return [3]

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

Adepth

Bdepth + 1

C-1

Ddepth - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning depth + 1 instead of depth when goal is found.

Appending neighbors with the same depth instead of incremented.

Returning 0 instead of -1 when goal is unreachable.

Return the current depth when goal is found.

Append neighbors with depth increased by 1.

Return -1 if goal is not reachable.