L'algorithme de Kruskal

Cet algorithme construit l'arbre en ajoutant à chaque itération l'arète de plus petit coût n'ajoutant pas de cycle. Comme il n'ajoute pas nécessairement des arêtes sur des sommets contigüs, cet algorithme peut être vu comme la fusion progressive d'une forêt (dont chaque arbre ne contient initialement qu'un seul sommet) en un seul arbre en ajoutant les arêtes de plus faible coût. Pour ce faire, on gagnera à effectuer préalablement un tri des arètes par coût croissant puis à considérer ces dernières dans l'ordre du tri.