CodeBlanks Logo Icon CodeBlanks
Login Register

BFS idea

Explore layer by layer from a start vertex.

BFS layers

Breadth-first search (BFS) starts at a source vertex and spreads layer by layer outward.

Each layer processes all vertices one step further. This makes BFS give the path with the fewest edges in an undirected graph.

BFS is often used for shortest path and reachability problems; it is implemented with a queue.

Order priority

BFS adds a vertex's neighbors to the queue when processed. First in, first out (FIFO) applies.

This way vertices with smaller distance are always processed first; the order stays intact.

Adding happens at the back, removal at the front; this preserves the layer order.

Practice Print layers

Write bfs_order(graph, start). List vertices in BFS visit order and return it. Print [0, 1, 2, 3] with print(bfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)).

Starter code

solution.py
def bfs_order(graph, start):
    # Return BFS visit order

Sample solution

solution.py
def bfs_order(graph, start):
    # Return BFS visit order
    visited = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            for nb in graph[node]:
                if nb not in visited:
                    queue.append(nb)
    return visited
print(bfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))

Expected output

[0, 1, 2, 3]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Which data structure does BFS use?

  • Stack
  • Queue Correct answer
  • Stack and queue
  • Heap

Explanation: Queue.

2 BFS start

Question 
queue = [____]
Answer 
queue = [start]

Explanation: start is right.

3 BFS idea: match the terms

Term Meaning
BFS Layer
queue FIFO
DFS Deep
heap Priority

All lessons in Intermediate

1 Merge sort

  1. Divide and conquer
  2. Merge operation
  3. Full merge sort
  4. Summary - Merge sort

2 Quick sort

  1. Pivot selection
  2. Partitioning
  3. Recursive quick sort
  4. Summary - Quick sort

3 Heap sort

  1. What is a heap?
  2. Heapify
  3. Build heap and sort
  4. Summary - Heap sort

4 Counting sort

  1. Counting idea
  2. Count array
  3. Output array
  4. Summary - Counting sort

5 Radix sort

  1. Radix idea
  2. Digit pass
  3. Stable sub-sort
  4. Summary - Radix sort

6 Sorting project

  1. Project: Overview
  2. Score array
  3. Apply merge sort
  4. Print statistics

7 Tree

  1. What is a tree?
  2. Node and edge
  3. Binary tree
  4. Summary - Trees

8 Binary search tree

  1. BST rule
  2. BST insert
  3. BST search
  4. Summary - BST

9 AVL tree

  1. Balanced tree
  2. Rotation
  3. Balance after insert
  4. Summary - AVL tree

10 Heap

  1. Min and max heap
  2. Insert
  3. Extract
  4. Summary - Heap

11 Priority queue

  1. What is a priority queue?
  2. Heap-based implementation
  3. Push and pop
  4. Summary - Priority queue

12 Data structures project

  1. Project: Overview
  2. Undo stack
  3. Pending queue
  4. Print the state

13 Graph basics

  1. What is a graph?
  2. Adjacency list
  3. Adjacency matrix
  4. Summary - Graph

14 Breadth-first search

  1. BFS idea
  2. Using a queue
  3. Marking visited
  4. Summary - BFS

15 Depth-first search

  1. DFS idea
  2. Stack or recursion
  3. Backtracking
  4. Summary - DFS

16 Greedy algorithms

  1. Greedy approach
  2. Coin change
  3. Greedy limits
  4. Summary - Greedy

17 Divide and conquer

  1. Three steps
  2. Recursive structure
  3. Master theorem
  4. Summary - Divide and conquer

18 Backtracking

  1. What is backtracking?
  2. State tree
  3. Pruning
  4. Summary - Backtracking

19 Graph project

  1. Project: Overview
  2. City graph
  3. BFS for reachability
  4. Print the result

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4