Un algoritmo para encontrar un «árbol recubridor mínimo» de un conjunto de puntos

ImgImgImgImg

Mike Bostrock tiene este algoritmo de Prim que trabaja sobre un conjunto de puntos aletatorios en el plano. Matemáticamente, el árbol recubridor mínimo (minimum spanning tree) es un grafo en forma de árbol que contiene todos los vértices – y los recorre según una distancia mínima, pero manteniéndolos siempre «conectados».

En la práctica esto por ejemplo sería la forma idónea en que una empresa de telecomunicaciones tendería sus cables de fibra óptica entre las viviendas de una ciudad: llegaría a todas partes y necesitaría una cantidad mínima de cable.

El código está en Observable (de donde Bostrock es fundador), que es una plataforma interactiva para analizar datos, visualizarlos y explorarlos, de modo que en la misma página pueda verse el código con todas sus funciones y variables y al mismo tiempo el resultado animado.

# Enlace Permanente

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

*

*