Graph Algorithms
Build a graph by clicking to place nodes and dragging between them to create edges. Then pick an algorithm and watch it think. BFS explores level by level. DFS dives deep and backtracks. Dijkstra and A* find shortest paths. Kruskal and Prim build minimum spanning trees. Each step is animated, and the algorithm’s internal data structures — queue, stack, priority queue, union-find — are shown in real time. The fundamentals of computer science, made visible.
Graphs Everywhere
A graph is nothing more than a set of objects (nodes) and connections between them (edges). This minimal structure turns out to be everywhere. Social networks are graphs — people are nodes, friendships are edges. The internet is a graph of routers and links. Road maps are graphs of intersections and streets. Protein interaction networks, airline routes, dependency trees in software, circuit boards, the web of hyperlinks you navigate daily — all graphs. Even the neurons in your brain form a graph of staggering complexity. Whenever you have things and relationships between things, you have a graph, and the algorithms on this page are the tools that let you ask questions about its structure.
BFS vs DFS
Breadth-First Search and Depth-First Search are the two fundamental ways to systematically explore a graph. BFS uses a queue: it visits all neighbors of the current node before moving deeper, expanding outward in concentric layers like ripples in water. This makes it ideal for finding shortest paths in unweighted graphs — the first time BFS reaches a node, it has found the shortest route. DFS uses a stack (or recursion): it plunges as deep as possible along one path before backtracking, exploring like a maze solver who always turns left. DFS is better for detecting cycles, finding connected components, and topological sorting. BFS requires O(V) space for its queue in the worst case; DFS requires O(V) for its stack. Both visit every edge once, running in O(V + E) time. The choice between them is about what you need, not which is faster.
Shortest Paths
Edsger Dijkstra published his shortest-path algorithm in 1959 — a three-page paper that became one of the most cited in computer science. The insight is greedy: maintain a set of nodes whose shortest distance from the source is known, and always expand the closest unknown node. Because edge weights are non-negative, once a node is finalized, no shorter path to it can exist. This greedy invariant is what makes Dijkstra’s algorithm correct. With a binary heap, it runs in O((V + E) log V) time. The algorithm fails with negative edge weights — for that, you need Bellman-Ford, which is slower but more general. Dijkstra’s algorithm is the backbone of every GPS navigation system, every network routing protocol, and countless optimization pipelines.
Minimum Spanning Trees
Given a connected, weighted graph, a minimum spanning tree (MST) is a subset of edges that connects all nodes with minimum total weight and no cycles. Kruskal’s algorithm sorts all edges by weight, then greedily adds the lightest edge that doesn’t create a cycle, using a union-find data structure to check connectivity in nearly O(1) time. Prim’s algorithm grows the tree from a single node, always adding the cheapest edge that connects a tree node to a non-tree node — essentially Dijkstra’s algorithm with edge weight instead of path distance. Both produce the same MST (when weights are unique) but through different strategies. MSTs appear in network design (minimizing cable length), clustering (remove the heaviest edges to find natural groups), and approximation algorithms for harder problems like the traveling salesman.
The A* Innovation
A* Search, published by Hart, Nilsson, and Raphael in 1968, augments Dijkstra’s algorithm with a heuristic — an estimate of the remaining distance to the goal. Instead of expanding the node with the smallest known distance g(n), A* expands the node that minimizes f(n) = g(n) + h(n), where h(n) is the heuristic estimate. If the heuristic never overestimates the true distance (a property called admissibility), A* is guaranteed to find the shortest path while typically exploring far fewer nodes than Dijkstra. In this visualizer, the heuristic is Euclidean distance — the straight-line distance between node positions on the canvas. A* is the algorithm behind pathfinding in video games, robotics, and any domain where spatial structure provides useful distance estimates.
Complexity and NP-Hardness
Every algorithm on this page runs in polynomial time — their running time grows manageably with input size. But many natural graph problems are NP-hard: no known polynomial-time algorithm exists, and most computer scientists believe none will ever be found. The Traveling Salesman Problem (find the shortest tour visiting every node exactly once) looks similar to shortest path but is exponentially harder. Graph coloring (color nodes so no two neighbors share a color, using the fewest colors) is NP-hard for three or more colors. Finding the largest clique, the longest path, or the minimum vertex cover — all NP-hard. The boundary between polynomial and NP-hard problems is one of the deepest questions in mathematics, formalized as the P vs NP problem. The algorithms here live on the tractable side of that boundary, which is precisely why they are so useful.