Algocraft · Theory

Graphs: nodes, edges, and never visiting twice

Almost every graph algorithm is a variation on the same sentence: explore connections systematically while remembering what you've already seen. BFS, DFS, Dijkstra, Prim, and Kruskal all follow that sentence — the differences between them are mostly about order (which neighbor to explore next) and what you're optimizing for (fewest hops, lowest total weight, cheapest way to connect everything). Get that framing straight and the five algorithms below stop looking like five things to memorize and start looking like one idea with four small twists.

01 · Foundation

Representing a graph

Before any traversal, search, or shortest-path logic can run, a graph has to live in memory somehow. There are two standard ways to store it, and picking the right one changes how efficient everything downstream is.

Adjacency list — a map (or array) from each node to the list of its neighbors. This is the practical default for almost everything: it only stores the edges that actually exist, so it's memory-efficient for sparse graphs (few edges relative to the number of possible pairs) — which is most real graphs.
Adjacency matrix — an n × n grid where cell (i, j) says whether an edge exists between node i and node j. Simpler to reason about, and gives O(1) "is there an edge here?" checks, but it costs O(n²) space no matter how few edges the graph actually has — wasteful once the graph is sparse and large.

Weighted edges don't change the shape of either representation much — in an adjacency list, each entry just becomes a (neighbor, weight) pair instead of a bare neighbor; in a matrix, the cell holds the weight instead of a boolean. Every algorithm below assumes one of these two representations is already built.

02 · Traversal

BFS vs. DFS — same exploration, different order

Both BFS and DFS visit every reachable node exactly once. The only real difference is the order they do it in, and that one difference in order is what makes each of them good at completely different jobs.

BFS (Breadth-First Search) uses a queue and explores level by level — every neighbor at distance 1 from the start, then every neighbor at distance 2, then distance 3, and so on. This level-by-level discipline is exactly why BFS finds the shortest path in an unweighted graph: it is structurally impossible for BFS to reach a node at distance 3 before it has exhausted every node at distance 1 and 2, so the first time it reaches any node is guaranteed to be via a shortest path.
DFS (Depth-First Search) uses a stack (explicit, or implicit via recursion) and plunges as deep as possible down one path before backtracking to try the next branch. It gives up any shortest-path guarantee, but that's fine — DFS is the right tool when you care about full exploration or structural properties, not distance: connectivity checks, cycle detection, and topological sort are all naturally DFS problems.

The diagram below shows one small graph, traversed with BFS starting at node A. Each node carries a number badge showing the order BFS actually visits it in — notice how A's direct neighbors (B, C) are both fully visited before either of their unvisited neighbors (D, E) gets touched, and F — two hops further out — is visited dead last.

Edges: A–B, A–C, B–D, B–E, C–E, E–F. Orange badges are BFS visit order from A. Both of A's neighbors (B, C — order 2, 3) are visited before either of their unvisited children (D, E — order 4, 5), and F, two hops out, is visited last (order 6) — the level-by-level pattern that guarantees shortest hop-count.

03 · Weighted shortest paths

Dijkstra — BFS, but weighted

Plain BFS finds shortest paths by hop count, which only works because every edge is worth exactly "1 step." As soon as edges have different weights (distances, costs, times), hop count stops meaning anything — the path with fewer hops isn't necessarily the cheapest one.

Dijkstra's shortest-path algorithm is BFS's natural generalization to that case. Swap the plain FIFO queue for a min-priority-queue keyed by "current best known distance from the start," and always expand whichever not-yet-finalized node currently has the smallest known distance. That's the entire algorithm: repeatedly pop the closest frontier node, relax (try to improve) the distances of its neighbors, and push any improvements back into the priority queue.

The greedy guarantee that makes this correct: once a node is popped from the priority queue, its distance is final — no later discovery can ever produce a shorter path to it, because every other path would have to route through a node that's already at least as far away. That guarantee only holds if every edge weight is non-negative. Introduce a negative edge and a "finalized" distance can retroactively become wrong, which is exactly why Dijkstra requires non-negative weights — graphs that do have negative edges need a different tool (Bellman-Ford), which trades Dijkstra's speed for tolerating negative weights.

04 · Minimum spanning trees

Prim vs. Kruskal — two ways to build a Minimum Spanning Tree

A Minimum Spanning Tree connects every node in a weighted graph using the smallest possible total edge weight, with no cycles. Prim and Kruskal both build one, greedily, but they greedily grow it in completely different shapes.

🌱 Prim — grow one tree outward

Start from any single node; that's the tree so far
Track the cheapest known edge from the tree to each frontier (not-yet-included) node, in a min-priority-queue
Repeatedly pop the cheapest frontier edge and add that node to the tree
After adding a node, update the frontier costs of its neighbors if it offers a cheaper connection
Stop once every node is in the tree

Conceptually close to Dijkstra — same "priority-queue of frontier candidates" shape — except it tracks per-edge weight instead of cumulative distance from the start. Good fit for dense graphs.

🧩 Kruskal — sort all edges globally

Ignore connectivity at first; sort every edge in the graph by weight, ascending
Walk the sorted list, cheapest edge first
Add an edge only if its two endpoints aren't already connected (checked with Union-Find / Disjoint-Set)
Skip any edge that would create a cycle
Stop once exactly n − 1 edges have been added

Dominated by the sort, not by how dense the graph is — so it's the better fit for sparse graphs, where there just aren't that many edges to sort.

One-line cross-link: Dijkstra, Prim, and Kruskal are also greedy algorithms at heart — see the Greedy theory page for the general greedy idea.

05 · Method

A repeatable framework for graph problems

Whatever the graph problem, working through these five questions in order gets you to the right algorithm before you write a line of code.

1 Represent the graphAdjacency list or matrix, weighted or unweighted — decide this first, since every algorithm below assumes it's already available.
2 Choose your traversal shapeBFS for shortest hop-count or level structure; DFS for exhaustive exploration, connectivity, or ordering constraints.
3 Weighted shortest path?Reach for Dijkstra with a min-priority-queue — as long as every edge weight is non-negative.
4 Need a Minimum Spanning Tree?Pick Prim (grows one tree, good for dense graphs) or Kruskal (sorts edges + union-find, good for sparse graphs).
5 Always maintain a visited setEvery algorithm on this page breaks — infinite loop, wrong answer, or wasted repeated work — the moment it revisits a node without checking whether it's already been processed.

06 · Patterns

Five graph algorithms, five visualizers

Each card links to the matching interactive visualizer, where you can watch the algorithm run step by step on a graph you can edit.

Breadth-First Search

queue: FIFO, level by level

Explores all neighbors at the current distance before moving further out — guarantees shortest path by hop count on unweighted graphs.

Try BFS →

Depth-First Search

stack / recursion, go deep first

Plunges down one path before backtracking. The natural fit for connectivity, cycle detection, and topological sort.

Try DFS →

Dijkstra's shortest path

pop closest, relax neighbors

BFS generalized to weighted, non-negative edges via a min-priority-queue keyed by current best distance.

Try Dijkstra →

Prim's MST

grow one tree, cheapest frontier edge

Starts from one node and expands outward, always adding the cheapest edge that reaches a new node. Good for dense graphs.

Try Prim's MST →

Kruskal's MST

sort edges, union-find, skip cycles

Sorts every edge globally, then greedily adds the cheapest ones that don't form a cycle. Good for sparse graphs.

Try Kruskal's MST →

07 · Worked example

Worked example — BFS traversal

Same graph as the diagram above (edges A–B, A–C, B–D, B–E, C–E, E–F), traced step by step from A. Neighbors are enqueued left-to-right and marked visited the moment they're enqueued, so a node can never be queued twice.

Step	Dequeued	Queue after	Visited so far
1	A	B, C	A, B, C
2	B	C, D, E	A, B, C, D, E
3	C	D, E	A, B, C, D, E
4	D	E	A, B, C, D, E
5	E	F	A, B, C, D, E, F
6	F	(empty)	A, B, C, D, E, F

Step 2 is the one worth staring at: dequeuing B discovers two new unvisited neighbors (D and E) in one step, both enqueued together. Step 3 dequeues C, whose only neighbors (A and E) are already visited, so nothing new is added — the queue only shrinks. This is why the visit order (A, B, C, D, E, F) matches the badge numbers in the diagram exactly: BFS finishes an entire distance level before touching the next one.

Open the BFS visualizer to watch a queue like this animate on a graph you can build yourself.

08 · Complexity

Complexity cheat-sheet

BFS / DFS — O(V + E). Every node is visited once and every edge is examined once (twice for undirected graphs, which is still a constant factor).
Dijkstra — O((V + E) log V) with a binary-heap priority queue: each of the up to E relaxations does an O(log V) heap operation.
Prim — O(E log V) with a heap-based priority queue for the frontier.
Kruskal — O(E log E), dominated entirely by sorting the edge list; each union-find operation afterward is near-O(1) amortized (with path compression and union by rank).

09 · Before you start coding

Common mistakes

Forgetting the visited set entirely — on any graph with a cycle, that turns into an infinite loop instead of a traversal.
Running Dijkstra on a graph with negative edge weights — it breaks the core greedy guarantee silently (no error, just a wrong "shortest" path). Use Bellman-Ford instead.
Implementing Kruskal without real cycle detection (union-find) — without it, you can silently build an invalid structure that isn't a tree at all, just a cyclic mess with the right edge count.
Reaching for DFS when the problem actually wants a shortest path — DFS guarantees it will eventually find a path, never that the first one it finds is the shortest.
Confusing "the order a graph's adjacency list happens to store neighbors in" with "visiting nearest neighbors first" — only unweighted BFS gives you that guarantee. DFS's visit order depends entirely on the traversal's depth-first shape, not distance.
Picking Prim on a very sparse graph (or Kruskal on a very dense one) — both produce a correct MST either way, but the "good fit" pairing above is where each one's complexity actually pays off.