Algorithme de Prim — arbre couvrant minimal

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

Graphe pondéré : $A - C (1)$ , $A - B (3)$ , $B - C (4)$ , $B - D (2)$ , $C - D (5)$ , $D - E (1)$ , $B - E (6)$ .

Appliquer Prim depuis $A$ .

— clique pour révéler

1 Indice 1

L'algorithme de Prim construit l'arbre en ajoutant, a chaque etape, l'arete de poids minimal reliant un sommet deja choisi a un sommet exterieur.

2 Indice 2

Commence par le sommet A et choisis a chaque etape la plus petite arete disponible vers l'exterieur de l'ensemble deja construit.

3 Indice 3

Additionne les poids des aretes selectionnees une fois tous les sommets atteints pour obtenir le poids total de l'arbre.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Validez votre réponse pour enregistrer votre progression et gagner des points