BFS and the FIFO Queue
In breadth-first search, the queue contains discovered nodes that have not yet been expanded.
-
Enqueue the starting node.
-
Remove the oldest node with popleft().
-
Enqueue each unvisited, reachable neighbor.
-
Stop when the goal is removed or the queue becomes empty.
Because every edge has equal cost, nodes are explored in increasing distance from the start. Nodes should normally be marked visited when enqueued; otherwise, they may enter the queue multiple times.
In Python, collections.deque is the expected implementation. Both append() and popleft() take O(1) time. Using list.pop(0) would make each removal O(n) because all remaining elements must shift left.
A* and the Priority Queue
A* also maintains a frontier, but it should not use an ordinary FIFO queue. Its frontier is a min-priority queue containing candidates ordered by:
f(n) = g(n) + h(n)
-
g(n) is the known cost from the start to n.
-
h(n) estimates the cost from n to the goal.
-
f(n) is the estimated cost of a complete path through n.
The candidate with the smallest f(n) is removed next. This allows A* to move toward the goal instead of exploring every node in breadth-first order. In Python, heapq implements a min-heap; heappush() and heappop() take O(log q) for a queue of size q.
For an optimal A* search, h(n) should be admissible: it must not overestimate the remaining cost. A consistent heuristic, which also satisfies |h(n) - h(m)| <= cost(n,m), prevents a settled node from needing to be reopened.
Queue Variants and Complexity
| Variant |
Typical use |
FIFO queue or deque |
BFS, buffering, task scheduling |
Priority queue or heapq |
A*, Dijkstra, ordered task processing |
| Circular queue |
Fixed-capacity FIFO systems |
| Monotonic deque |
Sliding-window maximum; not standard BFS or A* |
queue.Queue |
Thread-safe producer-consumer systems |
For a graph with V vertices and E edges:
| Algorithm |
Time |
Auxiliary space |
Reason |
| BFS |
Worst O(V + E); best O(1) when start is goal; average depends on goal depth |
Worst O(V); best O(1) |
In the worst case every reachable vertex is visited and every edge examined; the queue holds at most one level of nodes |
| A* with a consistent heuristic |
Best O(1) when start equals goal; average/worst upper bound O((V + E) log V) |
O(V + E) with duplicate heap entries; O(V) for a grid or with decrease-key |
Each priority-queue operation costs O(log V) |
These space bounds exclude the input graph and include the queue or heap. Recursion-stack space is O(1) because both implementations are iterative.
Worked Example
For a grid containing a wall, the frontier develops approximately as follows:
| Expanded node |
BFS FIFO frontier |
A* min-heap frontier |
Start (0, 0) |
[(0, 0)] |
(0, 0), f = 4.24 |
(0, 0) |
[(0, 1)] |
(0, 1), f = 4.61 |
(0, 1) |
[(0, 2)] |
(0, 2), f = 5.16 |
(0, 2) |
[(0, 3), (1, 2)] |
(1, 2), f = 5.24 and (0, 3), f = 6.00 |
BFS proceeds strictly by insertion order. A* selects the smallest f value and still finds the same shortest path in this unweighted grid.
Code Example
from collections import deque
from heapq import heappop, heappush
from math import hypot
Position = tuple[int, int]
Grid = list[list[int]]
def _validate(grid: Grid, start: Position, goal: Position) -> None:
if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
raise ValueError("Grid must be non-empty and rectangular")
rows, columns = len(grid), len(grid[0])
for position in (start, goal):
row, column = position
if not (0 <= row < rows and 0 <= column < columns):
raise ValueError("Position is outside the grid")
if grid[row][column] != 0:
raise ValueError("Start and goal must be traversable")
def _neighbors(grid: Grid, position: Position) -> list[Position]:
row, column = position
result: list[Position] = []
for row_delta, column_delta in ((1, 0), (-1, 0), (0, 1), (0, -1)):
next_row = row + row_delta
next_column = column + column_delta
if (
0 <= next_row < len(grid)
and 0 <= next_column < len(grid[0])
and grid[next_row][next_column] == 0
):
result.append((next_row, next_column))
return result
def _restore(
parent: dict[Position, Position | None], goal: Position
) -> list[Position]:
path: list[Position] = []
current: Position | None = goal
while current is not None:
path.append(current)
current = parent[current]
return path[::-1]
def bfs_path(grid: Grid, start: Position, goal: Position) -> list[Position]:
"""Return a shortest four-direction path in an unweighted grid."""
_validate(grid, start, goal)
frontier: deque[Position] = deque([start])
parent: dict[Position, Position | None] = {start: None}
while frontier:
current = frontier.popleft()
if current == goal:
return _restore(parent, goal)
for neighbor in _neighbors(grid, current):
if neighbor not in parent:
parent[neighbor] = current
frontier.append(neighbor)
raise ValueError("No path exists")
def astar_path(grid: Grid, start: Position, goal: Position) -> list[Position]:
"""Return a shortest path using A* with a consistent Euclidean heuristic."""
_validate(grid, start, goal)
def heuristic(position: Position) -> float:
return hypot(goal[0] - position[0], goal[1] - position[1])
distances: dict[Position, float] = {start: 0.0}
parent: dict[Position, Position | None] = {start: None}
closed: set[Position] = set()
sequence = 0
frontier: list[tuple[float, int, Position, float]] = [
(heuristic(start), sequence, start, 0.0)
]
while frontier:
_, _, current, current_cost = heappop(frontier)
if current in closed or current_cost != distances[current]:
continue
closed.add(current)
if current == goal:
return _restore(parent, goal)
for neighbor in _neighbors(grid, current):
tentative_cost = current_cost + 1.0
if tentative_cost < distances.get(neighbor, float("inf")):
distances[neighbor] = tentative_cost
parent[neighbor] = current
sequence += 1
heappush(
frontier,
(
tentative_cost + heuristic(neighbor),
sequence,
neighbor,
tentative_cost,
),
)
raise ValueError("No path exists")
grid = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 0],
]
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3)]
print(bfs_path(grid, (0, 0), (3, 3)))
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3)]
print(astar_path(grid, (0, 0), (3, 3)))
Common Pitfalls
-
Using list.pop(0) creates an O(n) queue operation; use deque.popleft().
-
Mark BFS nodes visited when enqueued to prevent duplicates and cycles.
-
Do not ignore stale A* heap entries after finding a cheaper route.
-
A* is not generally optimal with an inadmissible heuristic, and negative edge costs are incompatible with standard A* and Dijkstra.
-
Always handle an empty grid, an unreachable goal, and start == goal.
-
The code does not mutate the input grid, and parent maps support reconstructing the final path.