⌂ Home

🧠 Interactive BFS Tutorial

Click on Run Example BFS to see the algorithm traversal. Start the Interactive BFS after the example has completed!

Click on the correct nodes that follow the BFS traversal path. Complete the traversal and test your knowledge with a quiz!

Answer each question correctly with the knowledge you've accumulated. Move on to the coding activity when complete!

Fill in the blanks and run the code. Hints will be available on submission.

def bfs(graph, start):
    visited = set()
    queue = []   # blank #1
    while queue:
        node = queue.pop(0)   # dequeue from front
        if node not in visited:
            visited.add(node)
            # enqueue neighbors so they are explored in order
            queue.extend()
    return visited

Depth-First Search (BFS) — Pseudocode

      procedure BFS_recursive(G, start):
        visited ← set()
        parent  ← map()
        frontier ← [start]

        function explore(level):
            if level empty:
                return
            next ← []
            for u in level:
                if u ∉ visited:
                    visited.add(u)
                    for v in G.neighbors(u):
                        if v ∉ visited:
                            parent[v] ← u
                            next.append(v)
            explore(next)

        explore(frontier)
        return parent

  procedure BFS_iter(G, start):
    visited ← set()
    parent  ← map()
    Q ← queue([start])

    while Q not empty:
        u ← Q.dequeue()
        if u ∉ visited:
            visited.add(u)
            for v in G.neighbors(u):
                if v ∉ visited:
                    parent[v] ← u
                    Q.enqueue(v)
    return parent

Mentally trace the code to understand the algorithm's traversal pathing!