Algorithme de Prim
Arbre couvrant minimal
Enonce
Implémenter l'algorithme de Prim avec un tas (min-heap). Retourner la liste des arêtes de l'ACM et le poids total.
Signature attendue
def prim(G: dict) -> list:Exemple
prim({0: [(1, 1), (2, 4)], 1: [(0, 1), (2, 2)], 2: [(0, 4), (1, 2)]})→([(0, 1, 1), (1, 2, 2)], 3)
📖 Rappel de cours
L'algorithme de Prim construit un arbre couvrant minimal (ACM) en partant d'un sommet et en ajoutant à chaque étape l'arête de poids minimal reliant un sommet de l'arbre à un sommet extérieur.
Propriété de coupe :
Pour toute coupe $(S, V\setminus S)$, l'arête de poids minimal traversant la coupe appartient à un ACM.
Complexité :
$O((|V|+|E|)\log|V|) \text{ avec tas binaire}$
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Détection de Cycle dans un Graphe Non Orienté
- Tri Topologique
- Algorithme de Bellman-Ford
- Algorithme de Kruskal
- Coloration de Graphe
- Plus Court Chemin dans un Labyrinthe
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.