Algoritmul lui Kruskal

Este un algoritm care returneaza un arbore de acoperire minim pentru un graf ponderat (graf in care fiecare arc are asociat un cost).Un arbore de acoperire pentru un graf este un subgraf alcatuit din toate nodurile grafului initial dar nu din toate arcele, ci doar din atatea arce cat sa nu apara cicluri (altfel nu ar fi arbore)

Trebuie sa conectam 3 orase la o retea telefonica: Bucuresti, Timisoara si Arad
Necesar cablu: 1300 km
E inutil sa executam toate cele trei conexiuni, numai doua din ele sunt suficiente pentru o comunicare in bune conditii intre oricare 2 orase
De exemplu, legatura Timisoara – Arad ar putea lipsi, caz in care necesarul de cablu devine 1240 km