Breadth-first search

Breadth-first search is a graph traversal algorithm that visits vertices in order of increasing distance from a starting vertex, typically using a queue.

Queue (abstract data type): A queue is a collection that removes items in the order they were added, following first-in, first-out order. Breadth-first search processes each discovered vertex in arrival order.
Shortest-path problem: The shortest-path problem asks for a path of minimum total cost between specified vertices in a graph. Breadth-first search solves it when every edge has equal cost.
Depth-first search: Depth-first search explores one path as far as possible before backtracking to unexplored choices. It uses a stack-like strategy and does not generally find minimum-edge paths.
Graph theory: Graph theory is the mathematical study of vertices, edges, and the structures they form. Breadth-first search is a general method for exploring graph structures.
Konrad Zuse: Konrad Zuse was a German engineer and computer pioneer who built the Z3, an early programmable computer. His 1945 dissertation described a graph-traversal procedure recognized as breadth-first search.
Adjacency list: An adjacency list represents a graph by listing the neighbors of each vertex. The algorithm scans each vertex’s listed neighbors as it expands the frontier.
Maze-solving algorithm: A maze-solving algorithm finds a route through a maze represented as connected locations and passages. Breadth-first search finds a route with the fewest moves when each move costs the same.
Dijkstra's algorithm: Dijkstra’s algorithm finds shortest paths from one source when edge weights are nonnegative. It extends distance-prioritized exploration to graphs with unequal edge costs.
Vertex (graph theory): A vertex is a point in a graph that may be connected to other vertices by edges. Breadth-first search marks and processes vertices one at a time.
Zuse's dissertation: Konrad Zuse’s 1945 dissertation was a foundational work on calculating space, including methods for traversing graphs. It contains an early description of breadth-first graph traversal.

Linked from 21 pages