Understanding BFS Without Any Coding Experience

The problem is to find the shortest path in a 2‑D array of 0s (open) and 1s (obstacles) from the top‑left corner to the bottom‑right corner, moving only up, down, left or right.

Modeling and Algorithm Choice

Graph model: each cell is a node; adjacent cells share an edge.

Data structure: the grid itself represents the graph, and a queue implements BFS.

Algorithm: BFS is used because it explores nodes level by level, guaranteeing the first time the target is reached it is via the shortest path.

BFS Basics

BFS starts from a source node, visits all its neighbors, then proceeds to the next layer. It is typically implemented with a queue.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

The code imports deque, defines bfs, tracks visited nodes, and repeatedly pops the front of the queue, printing each node and enqueuing unvisited neighbors.

Friendly Walk‑through

The article rewrites the explanation with everyday analogies: the queue is a “first‑in‑first‑out line” like waiting for milk tea, and the visited set is a “list of places you’ve already been”. The process is broken into five steps—define the helper function, prepare the visited list, enqueue the start, explore neighbors, and repeat until the queue is empty.

Applying BFS to the Maze Problem

def shortest_path(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    directions = [(0,1),(1,0),(0,-1),(-1,0)]
    queue = deque([(start[0], start[1], 0)])
    visited = set()
    visited.add((start[0], start[1]))
    while queue:
        x, y, steps = queue.popleft()
        if (x, y) == end:
            return steps
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0 and (nx, ny) not in visited:
                queue.append((nx, ny, steps + 1))
                visited.add((nx, ny))
    return -1

The function extracts the grid size, defines the four movement vectors (right, down, left, up), and uses a queue that stores coordinates together with the current step count. It checks bounds, walkability (value 0), and whether a cell has been visited before enqueuing it.

grid = [
    [0,1,0,0],
    [0,0,0,1],
    [1,0,1,0],
    [0,0,0,0]
]
start = (0,0)
end = (3,3)
print(shortest_path(grid, start, end))  # outputs 6

The example returns 6, meaning the hero reaches the goal in six moves.

Direction Vectors Explained

(0, 1)

– move right one column. (1, 0) – move down one row. (0, -1) – move left one column. (-1, 0) – move up one row.

Using these tuples lets the algorithm add them to the current coordinate to obtain the neighbor’s position, simplifying the four‑direction traversal.

Why BFS Finds the Shortest Path

Because BFS processes nodes in order of increasing distance from the start, the first time the target cell is dequeued its associated step count is the minimal possible. Thus the algorithm returns the length of the shortest path.