Section 1 : Entrez les détails de votre carte

Étape 1 : Entrez le nom du point

Dans cette étape, vous devez entrer le nom de chaque point de votre carte. Le nom du point doit être unique.
Conditions

• Veuillez créer plus d'un seul sommet !

Vous devez créer au moins deux sommets pour créer une carte valide.

Étape 2 : Entrez le point de départ, le point d'arrivée et la distance

Dans cette étape, vous devez entrer le point de départ, le point d'arrivée et la distance entre les deux points. Le point de départ doit être différent du point d'arrivée.
Conditions

• Veuillez ne pas répéter la même association !

Vous ne pouvez pas créer deux associations identiques. Par exemple, vous ne pouvez pas créer une association entre le point A et le point B, puis une autre association entre le point B et le point A.

• Veuillez ne pas connecter un point avec lui même !

Vous ne pouvez pas créer une association entre un point et lui-même.

• Veuillez ne pas laisser un sommet isolé !

Chaque sommet doit être connecté à au moins un autre sommet.

Exemple :

Voici un exemple d'une carte valide :

Point de départ	Point d'arrivée	Distance
A	B	12
B	C	8

Dans cet exemple, la carte comporte trois sommets : A, B et C. Le point de départ est A, le point d'arrivée est B et la distance entre les deux points est de 10. Le point de départ est ensuite B, le point d'arrivée est C et la distance entre les deux points est de 20.

Remarques :

• Vous pouvez entrer les informations dans n'importe quel ordre.
• Les distances doivent être des nombres entiers.

Section 2 : Utilisation de la carte

Pour utiliser la carte, double-cliquez sur un cercle pour le sélectionner. Le cercle sélectionné sera entouré d'une bordure jaune. Une fois que vous avez sélectionné deux points, l'algorithme de recherche de chemin de Kruskal commence à fonctionner. Le chemin le plus court entre les deux points sera mis en évidence en surbrillance. Vous pouvez répéter ce processus autant de fois que vous le souhaitez. Vous pouvez annuler la sélection en cliquant sur un autre élément de la carte. Les associations afficheront des flèches pour indiquer le sens du trajet, car A -> B n'est pas égal à B -> A.

Section 3 : Algorithme utilisé

L'algorithme de Kruskal est un algorithme de recherche d'arbre couvrant de poids minimum (ARPM). Un arbre couvrant de poids minimum est un arbre qui relie tous les sommets d'un graphe avec le moins de poids possible. L'algorithme de Kruskal fonctionne en sélectionnant d'abord l'arête de poids le plus faible qui ne crée pas de cycle. Ensuite, l'algorithme sélectionne l'arête de poids le plus faible suivante qui ne crée pas de cycle, et ainsi de suite. Ce processus se poursuit jusqu'à ce que tous les sommets soient connectés.

Algorithme détaillé

1. Trier les arêtes par poids croissant.
2. Initialiser un ensemble de sommets vides.
3. Pour chaque arête, dans l'ordre du poids croissant :
   • Si les deux sommets de l'arête ne sont pas dans le même ensemble de sommets :
     • Ajouter l'arête à l'arbre couvrant de poids minimum.
     • Union des ensembles de sommets contenant les deux sommets de l'arête.

Temps d'exécution

Le temps d'exécution de l'algorithme de Kruskal est de O(E log E), où E est le nombre d'arêtes dans le graphe.

Applications

L'algorithme de Kruskal a de nombreuses applications, notamment :

• La conception de réseaux de télécommunications
• La construction de routes et de ponts
• La planification de circuits imprimés

Conclusion

L'algorithme de Kruskal est un algorithme efficace pour la recherche d'arbre couvrant de poids minimum. Il est simple à comprendre et à implémenter, et il a un temps d'exécution rapide. L'algorithme de Kruskal a de nombreuses applications pratiques.

Coder par        : Yasser Chenik
Algorithm par : Youness
Lien d'execution : https://yasser-chen.github.io/Dikstra/