BFS: breadth-first layers and shortest routes · 1 of 1
Breadth-first search
Use a first-in-first-out queue to visit vertices in distance layers and find fewest-move routes in graphs, grids and puzzle states.
Books1
Links6
- Shortest Paths with Unweighted Edges Solves Message Route with the distance and parent arrays, and has a graded list of BFS problems to practice on. usaco.guide (opens in a new tab)
- Breadth-first search The algorithm with parent arrays for route reconstruction, then the shortest cycle in a directed graph and the edges that lie on some shortest path. cp-algorithms.com (opens in a new tab)
- Lecture 9: Breadth-First Search Builds BFS from level sets, stores one parent per vertex to form a shortest-paths tree and proves the O(|V| + |E|) running time. ocw.mit.edu (opens in a new tab)
- BFS(图论) BFS order on trees and graphs, deque BFS for 0/1 weights and priority-queue BFS, with exercises. oi-wiki.org (opens in a new tab)
- Algorithms, Chapter 8: Shortest paths Section 8.4 runs breadth-first search in phases and proves that every distance it assigns is the length of a shortest path; the chapter goes on to Dijkstra and Bellman-Ford. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)
- Open Data Structures, Chapter 12: Graphs Adjacency matrices and adjacency lists compared operation by operation, then breadth-first and depth-first search on them. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code. opendatastructures.org (opens in a new tab)