Motivation

Alors que Kruskal trie toutes les arêtes globalement et utilise l'union-find, Prim conserve un seul arbre en croissance et cherche de manière répétée le sommet extérieur le plus proche.

Pourquoi apprendre Prim ?

• Graphes denses : Prim, avec les bonnes structures, est efficace lorsqu'il y a de nombreuses arêtes.
• Propriété de la coupe : c'est une illustration concrète de la raison pour laquelle l'arête la moins chère quittant l'arbre actuel peut toujours être ajoutée en toute sécurité.
• Deux visions d'un même problème : comparer Prim et Kruskal approfondit votre compréhension des arbres couvrant de poids minimal (MST).

Comme tous les MST d'un graphe partagent les mêmes poids d'arêtes, Prim et Kruskal rapportent toujours le même poids total.