Analyzing Spanning Trees

100%

Analyzing Spanning Trees

✓ Published0🌍 Public

Last edited Feb 9, 2016

Created on May 13, 2014

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.

AI-generated description

These histograms show great-grandchildren counts for spanning trees generated by various algorithms. Randomized depth-first traversal has a strong tendency to generate long non-branching passages, where most nodes only have one child.

gpl-3.0 Licensed

Similar vizzes

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

70% match

Loading thumbnail…

Random Traversal IV

This example shows a tree layout applied to a recursively generated maze, producing a branching structure of connected cells. The maze is created using a randomized depth-first traversal that records edge connections, and the resulting tree is rendered as a set of black link paths. The code uses `d3.layout.tree` to compute node positions from the maze’s traversal tree, then draws each link as an SVG path with `M` and `L` commands. The visualization is built with D3 v3 and SVG, with the maze generation logic implemented in plain JavaScript.

Mmbostock

68% match

Loading thumbnail…

Randomized Depth-First IV

A maze is generated on a 40x40 grid using a randomized depth-first traversal, then converted into a tree structure. The tree layout from D3 is applied to position the nodes, and SVG paths draw the links between parent and child nodes. The code uses `d3.layout.tree`, `d3.select`, and SVG path elements to render the final hierarchical visualization. The tree’s branching pattern visually reflects the maze’s corridors and dead ends, with each node representing a cell and each link a passage.

Mmbostock

68% 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

67% match

Loading thumbnail…

Wilson’s Algorithm IV

Wilson’s Algorithm IV applies D3’s tree layout to a maze generated by Wilson’s loop-erased random walk. The maze is represented as a hierarchical tree of connected cells, with SVG paths drawn as straight links between parent and child nodes. The code uses `d3.layout.tree`, `tree.nodes`, and `tree.links` to compute positions, while custom functions `generateMaze` and `generateTree` construct the maze’s spanning tree. The visualization shows the resulting tree structure with black connecting lines against a white background, using D3 v3 and SVG rendering.

Mmbostock

67% 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

67% match

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

66% match

Loading thumbnail…

Voronoi Spanning tree - long paths

This example visualizes a Voronoi spanning tree using a dataset of 1,500 randomly generated sites. A red line connects each site to its nearest neighbor in the direction of a user-controlled root point, which follows the mouse cursor. The resulting tree reveals long, winding paths as the connection logic prioritizes proximity to the root over local clustering. Built with d3.v4 and the d3.voronoi API, it renders SVG polygons for the diagram and lines for the spanning tree, updating dynamically on mouse movement.

PPhilippe Rivière

66% match