Retour au Portfolio

Algorithme de Kruskal

Implémentation Java (Console + GUI) — Minimum Spanning Tree

Description du Projet

Implémentation de l'algorithme de Kruskal en Java (JDK 17). Le projet propose une version console pour saisir sommets et arêtes, et une interface graphique (Swing) pour construire visuellement un graphe, exécuter l'algorithme et visualiser l'arbre couvrant minimal (MST).

L'objectif est d'illustrer une approche pédagogique : tri des arêtes par poids, structure Union‑Find (sous‑ensembles), et sélection des arêtes minimales sans créer de cycles.

Technologies Utilisées

Java 17 Swing Algorithme : Kruskal Union‑Find MST Git

Fonctionnalités Principales

  • Mode console : saisie de sommets/arêtes et calcul du MST avec sortie texte.
  • Interface graphique (Swing) : ajouter des sommets par clic, créer des arêtes pondérées, exécuter Kruskal et visualiser le MST.
  • Visualisation interactive des arêtes sélectionnées pour le MST.
  • Implémentation robuste de Union‑Find (union by rank + path compression).
  • Réinitialisation du graphe et réexécution aisée pour tester plusieurs instances.

Captures d'écran

Interface graphique - ajout de sommets
Interface GUI
Ajout de sommets et création d'arêtes dans l'interface graphique.
Visualisation du MST
MST Visualisé
Résultat : arêtes sélectionnées formant l'arbre couvrant minimal (MST).

Liens du Projet

Code Source README

Défis et Solutions

Défi : Fournir une implémentation claire et performante pour des graphes de taille variable.

Solution : Tri efficace des arêtes et utilisation d'un Union‑Find optimisé (union by rank + path compression).

Défi : Rendre l'outil accessible pour démonstration pédagogique.

Solution : Interface GUI simple avec actions claires : ajouter sommets, lier arêtes, exécuter et réinitialiser.

Défi : Diffuser l'exemple de manière autonome.

Solution : Fournir une version console et une GUI autonome, compatible JDK 17.