Graph algorithms

Breadth-first and depth-first search differ by one data structure; Dijkstra and A* differ by one term in a comparison. Neither difference is visible in prose, so the frontier — the queue, the stack or the priority queue — is drawn as its own track beside the graph, with the item being taken marked. Choose the graph, from a seed, and a link you share draws exactly the graph you were looking at.

8 algorithms

Breadth-first searchA queue, taken from the front.Explores a graph level by level from one starting node, keeping the nodes it has reached but not yet examined in a queue, so the first time it arrives anywhere is by a path with the fewest possible edges.O(V + E)O(V) space
Depth-first searchA stack, taken from the top.The same loop as breadth-first search with the queue replaced by a stack, so it commits as deep as it can before backing out — and reaches most nodes by paths that are not shortest.O(V + E)O(V) space
DijkstraA priority queue, smallest cost first.Settles nodes cheapest-first out of a priority queue, so a node is only final once it has been taken — which is what lets it handle edges of different costs, and what breaks the moment a cost is negative.O(E + V log V)O(V) space
A*A priority queue, smallest cost-plus-estimate first.Dijkstra with one extra term: the queue is ordered by the cost so far plus an estimate of the cost remaining, which pulls the search towards the target instead of spreading evenly in every direction.O(E)O(V) space
Topological sortA queue of nodes with nothing left before them.Produces an order in which every edge points forwards, by repeatedly taking a node with nothing left before it — and reports honestly that no such order exists when a cycle means there is none.O(V + E)O(V) space
KruskalA sorted edge list, and the disjoint sets themselves.Sorts every edge by weight and takes each one unless it would close a cycle, deciding that with a union-find over the nodes — and the disjoint sets are drawn, because they are the algorithm.O(E log E)O(V) space
PrimA priority queue of the edges leaving the tree.Grows one connected tree from a single vertex, repeatedly taking the cheapest edge that leaves it — the same minimum spanning tree as Kruskal from the opposite strategy.O(E log V)O(V) space
Bellman-FordNo frontier at all: the whole edge list, swept in order.Relaxes every edge in the graph, over and over, V−1 times — which is slower than Dijkstra and survives the negative weights Dijkstra cannot, and detects a negative cycle rather than returning nonsense.O(V · E)O(V) space

Sorting and searching live next door in AlgoLab, the call stack inRecursion, and pattern matching in String matching.