Exercices de programmation pour classes préparatoires
Écrire une fonction kruskal : int -> (int * int * int) list -> (int * int * int) list qui calcule un arbre couvrant de poids minimal (ACM) d'un graphe pondéré connexe.
Les arguments sont :
- n : nombre de sommets (numérotés de 0 à n-1),
- aretes : liste des arêtes sous la forme (u, v, poids), chaque arête n'apparaissant qu'une seule fois (graphe non orienté).
La fonction renvoie la liste des arêtes sélectionnées par l'algorithme de Kruskal, triées par poids croissant. En cas d'égalité de poids, l'ordre relatif n'a pas d'importance ; pour l'évaluation, on garantit que les poids des arêtes de l'ACM sont distincts (les tests ne présentent pas d'ambiguïté).
L'idée de l'algorithme : trier les arêtes par poids croissant, puis les parcourir dans cet ordre en gardant celles qui relient deux composantes connexes différentes. On utilisera une structure Union-Find (ou un tableau de parents avec une fonction find récursive).
On suppose le graphe connexe ; l'ACM contient donc exactement n - 1 arêtes. Si n = 1, l'ACM est vide.
| Appel | Résultat attendu |
|---|---|
| kruskal 1 [] | [] |
| kruskal 3 [(0, 1, 1); (1, 2, 2); (0, 2, 3)] | [(0, 1, 1); (1, 2, 2)] |
Connectez-vous pour soumettre du code.