Una compañía de televisión por cable pretende dar servicio a un nuevo barrio de la ciudad. Tiene restricciones impuestas por el ayuntamiento, de manera que sólo puede echar el cable por algunas de las calles. Además, algunas de las conexiones posibles entre las casas serían muy costosas, por ser demasiado largas o por requerir un soterramiento demasiado profundo. Así que la compañía tiene que calcular la forma más barata de llegar a todas las casas por medio del cable.

La solución de este problema se obtiene representando las conexiones posibles entre las casas con un grafo (las casas serían los vértices y las aristas las calles por las que se tiene permiso para echar el cable), y calculando el árbol de recubrimiento de peso mínimo (minimum spanning tree).

Los dos algoritmos más conocidos para resolver el problema anterior, el de Prim y el de Kruskal, son ejemplos típicos de algoritmos voraces. En esta asignatura veremos en qué consiste el esquema voraz de resolución de problemas y en qué casos da lugar a algoritmos correctos y por qué.

Haz clic en la imagen inferior para ver un applet que resuelve el problema.