L'algorithme de Kruskal consiste en la construction de l'arbre :
-
Au départ, l'arbre de poids minimum est vide.
-
Ranger les arcs du graphe dans l'ordre des poids croissants dans un tableau (une variante est possible aussi dans une liste chaînée). Puis pour chaque arc, si celui-ci ne forme pas de cycle avec les arcs déjà retenus dans l'arbre, on rajoute l'arc dans l'arbre.
On considère un graphe dont les sommets sont des entiers consécutifs, le plus petit d'entre eux étant le sommet 1. Le graphe n'est pas nécessairement complet, les poids sont des entiers ou des flottants.
Exemple : L'arbre obtenu pour cet exemple est le suivant :
Cahier des charges
-
Les seules variables globales autorisées seront l'ordre et la taille du graphe.
-
Les tableaux seront alloués dynamiquement.
-
L'ordre, la taille, la liste des arêtes (2 extrémités) du graphe et leur poids seront lus dans un fichier sous la forme suivante :
9
16
1 2 1
2 3 7
…
Vous lirez le graphe arête par arête, en faisant correspondre à chaque arête une structure contenant les
noms des deux extrémités de l'arête et son poids ; chaque triplet sera ajouté dans un tableau (ou liste )
Travail à faire
1) Exécutez à la main l'algorithme de Kruskal du cours pour cet exemple
• Algorithme à coder :
• Vous stockerez l'ensemble des arêtes dans un tableau (ou une liste chaînée) que vous trierez par poids croissants
• On construit au fur et à mesure l'arbre en partant de l'ensemble des sommets et d'un ensemble vide d'arêtes :
• Vous numéroterez les sommets pour que, au fur et à mesure de l'algorithme, deux sommets aient même numéro s'ils appartiennent à une même composante connexe de l'arbre en construction. Pour cela, on attribue au départ le numéro i au sommet i.
• Vous ajouterez à l'arbre les arêtes en suivant le tableau (ou liste ) trié mais en "sautant" les arêtes dont les extrémités ont même numéro (qui appartiennent donc à une même composante connexe). Lorsqu'on ajoute une arête, on note num1 et num2 les numéros de ses extrémités : tout sommet ayant comme numéro num2 voit changer son numéro en num1.
Attention : pensez que si votre 1 er numéro de sommet est 1, un tableau démarre à la position 0.
• Enfin, on détectera le cas où le graphe n'est pas connexe (pas de cycle donc pas de solution), et on indiquera cela uniquement à l'écran
• Les résultats seront affichés à l'écran et aussi sauvegardés dans un fichier dont on demandera le nom à l'utilisateur. |
