Algorithme de Kruskal
Arbre couvrant minimal avec Union-Find
Enonce
Implémenter Kruskal avec Union-Find (compression de chemin + union par rang). Retourner les arêtes de l'ACM.
Signature attendue
def kruskal(sommets: list, aretes: list) -> list:Exemple
kruskal([0, 1, 2], [(0, 1, 1), (1, 2, 2), (0, 2, 4)])→([(0, 1, 1), (1, 2, 2)], 3)
📖 Rappel de cours
L'algorithme de Kruskal trie les arêtes par poids croissant et les ajoute une par une si elles ne créent pas de cycle, en utilisant la structure Union-Find.
Union-Find :
find(x) : trouver la racine (avec compression de chemin).
union(x,y) : fusionner deux composantes (avec rang).
Complexité :
$O(|E|\log|E|) \text{ (dominé par le tri des arêtes)}$
⚠ Le piège : Sans compression de chemin ni union par rang, l'Union-Find dégénère en liste chaînée et le coût s'effondre. Avec les deux, chaque opération est quasi constante. Kruskal trie les arêtes — il est à son avantage sur un graphe creux, là où Prim l'emporte sur un graphe dense.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Tri Topologique
- Algorithme de Bellman-Ford
- Algorithme de Prim
- Coloration de Graphe
- Plus Court Chemin dans un Labyrinthe
- Représentations d'un Graphe
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.