Traversals, shortest paths, spanning trees, and connectivity on interactive graphs.
59 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.
Runs BFS from both endpoints and joins the first intersecting shortest-path frontiers.
Repeats depth-limited DFS with increasing limits to find a shallow target using DFS-sized memory.
Finds vertices whose removal increases the number of connected components.
Finds edges whose removal increases the number of connected components.
Two-colors every component and reports the first edge whose endpoints require the same color.
Uses every directed edge exactly once after validating degree and weak-connectivity conditions.
Searches for a path visiting every vertex exactly once and visualizes every choice and backtrack.
Combines Bellman-Ford reweighting with one Dijkstra run per vertex and detects negative cycles.
Queue-optimizes Bellman-Ford by rescanning only vertices whose distances improve.
Finds shortest residual augmenting paths with BFS and pushes each path's bottleneck flow.
Alternates residual BFS level graphs with DFS blocking flows until the sink becomes unreachable.
Computes shortest paths with a deque when every edge weight is zero or one.
Uses distance buckets for nonnegative bounded integer edge weights.
Runs synchronized Dijkstra searches from both endpoints.
Relaxes vertices once in topological order and accepts negative edges.
Repeatedly adds each component's cheapest outgoing edge.
Deletes heavy edges whenever component connectivity is preserved.
Builds a directed Euler trail by splicing edge-disjoint circuits.
Constructs an undirected Euler trail while avoiding bridges when possible.
Finds maximum bipartite matching in BFS-layered augmenting batches.
Computes a minimum-cost perfect assignment using dual potentials.
Repeatedly contracts random edges and retains the lightest sampled cut.
Deterministically computes the global minimum cut in a weighted undirected graph.
Iteratively distributes rank through incoming links with dangling-node correction.
Enumerates every maximal clique using pivoted backtracking.
Finds a minimum rooted directed spanning arborescence by contracting cycles.
Computes all directed reachability pairs with Warshall's recurrence.
Uses DFS low-link values and an edge stack to emit biconnected blocks.
Detects a directed cycle through white, gray, and black DFS states.
Computes maximum flow with local excess pushes and admissible height labels.
Augments flow along shortest reduced-cost residual paths.
Produces a stable matching by deferred acceptance proposals.
Finds maximum matching in general graphs by contracting odd blossoms.
Answers a batch of lowest-common-ancestor queries with DFS and disjoint sets.
Encodes every pairwise minimum cut of an undirected graph in a weighted tree.
Finds two edge-disjoint shortest paths through reweighting and cancellation.
Repairs a shortest path incrementally when traversability costs change.
Reuses g and rhs values across a sequence of related shortest-path searches.
Expands the minimum f=g+h frontier state.
Expands density-connected epsilon neighborhoods.
Iterates stochastic link transitions with teleportation.
Uses BFS augmenting paths and residual updates.
Builds level graphs and sends blocking flows.
Tracks discovery, low-link, and active-stack invariants.
Batches shortest alternating augmenting paths.
Consumes every edge and stitches Eulerian cycles.