Breadth First Search Path Finding - Store Paths in Queue or Track Predecessors? In studying various solutions for finding a path in a 2d maze using BFS, I've come across two different approaches. One is to store the whole path to a given position in the search queue. The other is to keep track of predecessors and build the path at the end by back-tracking.

I'm curious to hear which of these approaches is considered better in which situations. It looks to me like the time and memory requirements for the "store the path in the queue" method would grow much faster than the "predecessors" approach as the maze grows in size. Is that correct?

Below are two implementations in Python showing the different approaches.

"""
BFS maze solver.
The queue contains paths.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([[start]])
    seen = set([start])
    while queue:
        print("queue:", queue)
        path = queue.popleft()
        print("path", path)
        i, j = path[-1]
        if grid[i][j] == goal:
            return path
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 &lt;= i2 &lt; num_rows and 0 &lt;= j2 &lt; num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append(path + [(i2, j2)])
                seen.add((i2, j2))

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
path = bfs(grid, (0, 0))


"""
BFS maze solver.
The queue contains only positions. Predecessors are kept in dictionary.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([start]) #!!
    seen = set([start])
    while queue:
        print("queue:", queue)
        i, j = queue.popleft()
        print("i, j:", i, j)
        if grid[i][j] == goal:
            return (i, j)
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 &lt;= i2 &lt; num_rows and 0 &lt;= j2 &lt; num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append((i2, j2))
                seen.add((i2, j2))
                previous[(i2, j2)] = (i, j)

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
start_pos = (0, 0)
previous = {}
previous[start_pos] = (-1, -1)
goal = bfs(grid, start_pos)

if goal:
    path = []
    i, j = goal
    while i != -1:
        path.append((i, j))
        i, j = previous[(i, j)]
    path.reverse()
    print("----Node history---")
    for item in previous.items():
        print(item)
    print("----Path----")
    print(path)
```
There's no set answer, as it depends on the number of nodes in the graph, the average number of nodes in the queue at any point in time, and the average length of paths.

"Considered better" is a matter of opinion, and on this site, we focus on technical questions rather than opinion.

If it were me, I would use predecessor pointers as my default, unless I had careful measurements showing that on my workload the other was better.