frontier
The set of discovered but not yet processed vertices at the edge of a search, waiting in its queue, stack or heap.
In more detail
In BFS the frontier is a FIFO queue, so it expands in waves. In Dijkstra's and Prim's algorithms it is a min-heap ordered by cost, so the cheapest option is processed next.
Related terms
- breadth-first search — A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.
- Dijkstra's algorithm — An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
- Prim's algorithm — An algorithm that builds a minimum spanning tree by growing it from one start vertex, always adding the cheapest edge leading out of the tree.
Taught in
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers