Algorithms · topic
BFS and DFS on adjacency lists and matrices, BFS levels, DFS discovery and finish times, edge classification, topological sort, connected and strongly connected components, cycle detection, bipartite testing, articulation points and bridges.
Breadth-first search (BFS) explores a graph level by level from a source s: it visits every vertex at distance k before any vertex at distance k+1. The search builds a BFS tree of shortest paths in the unweighted sense (fewest edges) and assigns each reachable vertex a distance d[v] = δ(s,v).
Depth-first search (DFS) explores a graph by going as deep as possible along each path before backtracking. It assigns every vertex a discovery time d[u] and a finish time f[u], and it classifies every edge as a tree, back, forward or cross edge.
Two classical applications of DFS finish times are topological sort of a directed acyclic graph (DAG) and the computation of strongly connected components (SCCs) of a directed graph. A topological order lists vertices so that every edge goes forward in the list.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
