Prim’s Algorithm

100%

Prim’s Algorithm

✓ Published0🌍 Public

Last edited Feb 9, 2016

Created on Apr 21, 2014

Prim’s Algorithm visualizes the construction of a minimum spanning tree on a grid of randomly weighted edges. A magenta frontier expands from the bottom-left corner, with d3.timer driving the step-by-step animation. Each iteration pops the lowest-weight edge from a custom minHeap, adds it to the tree, and updates the frontier on a canvas. The rendering uses manual Canvas 2D fillRect calls to draw cells and connections, with black indicating unexplored space and white showing the growing tree.

AI-generated description

Prim’s algorithm generates a minimum spanning tree from a graph with weighted edges. Starting in the bottom-left corner, the algorithm keeps a heap of the possible directions the maze could be extended (shown in pink). At each step, the maze is extended in the direction with the lowest weight, as long as doing so does not reconnect with another part of the maze. Here the edges are initialized with random weights.

Unlike Wilson’s algorithm, this does not result in a uniform spanning tree. Sometimes, random traversal is misleadingly referred to as randomized Prim’s algorithm; however, the two algorithms exhibit radically different behavior! The global structure of the maze can be more easily seen by flooding it with color.

gpl-3.0 Licensed

Similar vizzes

Loading thumbnail…

Prim’s Algorithm IV

The visualization displays an animated spanning tree generated by Prim’s algorithm on a maze, with colors cycling through a cubehelix color scale to highlight the tree's structure. The maze is computed asynchronously in a worker thread using a min-heap priority queue. The animation renders to a Canvas via `putImageData`, updating pixel colors every 20 milliseconds based on each cell's distance from the start, while rotating the hue through 360 degrees. D3.js (v3) provides the cubehelix interpolation and animation timing.

Mmbostock

84% match

Loading thumbnail…

Prim’s Algorithm V

A maze-like spanning tree fills a canvas, with its cells colored by a continuously cycling cubehelix color scale based on tree depth. The scale’s periodicity shifts over time, alternately emphasizing fine-grained local details and broader structural patterns. The visualization uses a Web Worker to generate the maze via Prim’s algorithm, then renders the result to a Canvas 2D context using `putImageData`, with animation driven by `d3.timer`.

Mmbostock

83% match

Loading thumbnail…

Prim’s Algorithm III

The visualization shows a spanning tree of the canvas generated with Prim’s algorithm, then flooded with color from the root; hue encodes Manhattan distance, creating a distinctive gradient pattern. A Web Worker computes the maze structure using a custom binary min-heap priority queue, while the main thread animates the flood fill via `d3.timer` and writes pixel data directly into a Canvas `ImageData` object. The animation cycles through hues by incrementing a distance counter and calling `context.putImageData` each frame.

Mmbostock

82% match

Loading thumbnail…

Prim’s Algorithm IV

This example visualizes a random maze as a tree, generated using Prim’s algorithm with a randomized priority queue. The path from the root (bottom-right cell) to every other cell branches into a tidy, non-crossing layout produced by the D3 tree layout (`d3.layout.tree`). Links are drawn as straight SVG paths from each parent to its child. The maze itself is built by a custom `minHeap` implementation that selects edges with random weights, ensuring a uniformly random spanning tree.

Mmbostock

81% match

Loading thumbnail…

Prim’s Algorithm II

This example generates a maze using Prim’s algorithm and floods it with color to visualize Manhattan distance from the starting cell. As the animation progresses, a hue-changing fill pulses over frontier cells, highlighting the maze’s structure and growth pattern. The maze is drawn to a Canvas 2D context, with each cell and connecting wall filled via `fillRect`. The implementation uses D3 v3’s `d3.timer` for animation and `d3.hsl` for color encoding, while the maze generation relies on a custom binary heap for priority-based frontier expansion.

Mmbostock

78% match

Loading thumbnail…

Wilson’s Algorithm

Wilson’s Algorithm visualizes the construction of a uniform spanning tree via loop-erased random walks on a black canvas. A magenta path grows until it connects to the existing white maze, with loops erased and reconnecting cells turned white. The animation uses a Canvas context with `fillRect` for cells and corridors, managed by `d3.timer`, `d3.range`, and the `globalCompositeOperation` property for path erasure. Starting from one cell, the process accelerates as the maze expands, revealing the tree’s structure.

Mmbostock

66% match

Loading thumbnail…

Analyzing Spanning Trees

Four histograms compare the distribution of great-grandchild counts in spanning trees generated by four maze algorithms: randomized depth-first traversal, random traversal, Prim's algorithm, and Wilson's algorithm. Each horizontal bar group shows the probability of a node having zero through eight great-grandchildren across a 200×200 grid. The visualization reveals that randomized depth-first traversal strongly favors long, non-branching passages with many zero-count nodes. The code uses d3.svg.axis, d3.scale.ordinal, and d3.tsv to render the computed data from a TSV file.

Mmbostock

64% match

Loading thumbnail…

Voronoi Spanning tree - short paths

The visualization draws a Voronoi spanning tree that connects 1,500 randomly placed sites by hopping from each site to a neighboring site closer to a moving root point. As the mouse moves, the tree’s edges recompute in real time, highlighting short paths toward the cursor. Built with D3 v4, it uses `d3.voronoi` to compute cells and edges, with a custom `diagram.find()` and `diagram.next()` method to traverse the diagram. The SVG rendering shows semi-transparent polygon boundaries and black spanning lines, with red highlighting on found cells.

PPhilippe Rivière

64% match