Traversals, shortest paths, spanning trees, and connectivity on interactive graphs.
13 visualizations
Explores a graph level by level from a source using a queue — the basis of unweighted shortest paths.
Explores each branch as deeply as possible before backtracking — the basis of many graph algorithms.
Finds shortest paths from a source in a non-negative weighted graph by always settling the closest frontier node.
Grows a minimum spanning tree from a start node by repeatedly adding the cheapest edge to a new vertex.
Sorts all edges by weight and adds each one that doesn't create a cycle, using union-find to detect cycles.
Orders the vertices of a DAG so every edge points forward, by repeatedly removing in-degree-zero nodes.
Finds shortest paths from a source even with negative edges by relaxing all edges V−1 times, and detects negative cycles.
Computes shortest paths between every pair of vertices by progressively allowing more intermediate vertices.
Maintains a partition of elements into disjoint sets with near-constant-time union and find via rank and path compression.
Finds all strongly connected components of a directed graph in a single DFS using discovery indices and lowlink values.
Finds strongly connected components with two DFS passes: order by finish time, then DFS the transposed graph.
Finds the shortest path on a grid by expanding the cell that minimizes f = g + h, guided by an admissible heuristic.
Computes the maximum flow from source to sink by repeatedly pushing flow along shortest augmenting paths found with BFS.