A frontier holds discovered states that remain candidates for exploration. In a maze search, it begins with the start location. The search removes a node, tests its state against the goal, and adds eligible successors. A separate explored collection tracks states already encountered so the search does not circle back indefinitely. section 2.2
How the frontier removes nodes determines the search order:
- Depth-first search uses a stack, taking the most recently added node and following a path deeper before backtracking. section 2.2
- Breadth-first search uses a queue, taking the earliest added node to explore nearby locations first. section 2.2
- A* uses a priority queue of nodes with costs and heuristics. section 2.2
Each node keeps its state and parent. When the goal is removed from the frontier, following parent links reconstructs the path. If the frontier empties first, there is nowhere left to search. section 2.2
func dfs<StateType:
Hashable>(initialState: StateType, goalTestFn: (StateType)
-> Bool, successorFn: (StateType) -> [StateType]) -> Node<StateType>? {
// frontier is where we've yet to go
let frontier: Stack<Node<StateType>> = Stack<Node<StateType>>()
frontier.push(Node(state: initialState, parent: nil))
// explored is where we've been
var explored: Set<StateType> = Set<StateType>()
explored.insert(initialState)
// keep going while there is more to explore
while !frontier.isEmpty {
let currentNode = frontier.pop()
let currentState = currentNode.state
// if we found the goal, we're done
if goalTestFn(currentState) { return currentNode }
// check where we can go next and haven't explored
for child in successorFn(currentState) where
!explored.contains(child) {
explored.insert(child)
frontier.push(Node(state: child, parent: currentNode))
}
}
return nil // never found the goal
}
The Swift depth-first search keeps its frontier as a stack of nodes and its explored states in a separate set. section 2.2
