Two-ended BFS expansion to demonstrate frontier intersection optimization.
Easy Explanation
Bidirectional BFS searches from both start and goal at once, meeting in the middle to reduce explored area.
Renderer Mode
`Simple` uses abstract, short-form-friendly visuals. `Advanced` keeps the current detailed view.
Grid
n/a
Visited
n/a
Meeting
n/a
Result
Searching
Safe mode: choose a tool to edit the grid.
Press Play or Step to start execution.
function bidirectional_bfs(graph, start, target):
if start == target:
return [start]
forward_queue <- [start]
backward_queue <- [target]
forward_parent[start] <- none
backward_parent[target] <- none
forward_seen <- { start }
backward_seen <- { target }
while forward_queue not empty and backward_queue not empty:
active_direction <- choose_frontier(forward_queue, backward_queue)
for each node in current_layer(active_direction):
for neighbor in neighbors(node):
if neighbor already seen by active_direction:
continue
record parent for neighbor in active_direction
if neighbor seen by opposite_direction:
return stitch_paths(forward_parent, backward_parent, neighbor)
mark neighbor seen
push neighbor into active frontier
return no path