Classe Union Find et algorithme de Kruskal - Java

Required Files: Executable.java, maison.txt, maisonUnitaire.txt, Arete.java, GraphePondere.java, Partition.java (Download)
Maximum number of files: 12
Type of work: Individual work

Soit G un graphe pondéré. On cherche un arbre couvrant de poids minimum de G. L'algorithme  construit un autre graphe pondéré K qui contient les mêmes sommets que G et une partie des arêtes de G. Le graphe K ne contient pas de cycle (c'est un arbre). L'algorithme de Kruskal qui permet de trouver un arbre couvrant de poids min est le suivant :

  1. créer un graphe K, de même nombre de sommets que G, sans arête
  2. trier les arêtes de G par poids croissant
  3. pour chaque arête (x,y) de G (prise par ordre de poids croissant) si x et ne sont pas dans la même composante connexe dans K ajouter l'arête (x,y) au graphe K (noter que x et y sont à présent dans la même composante de K).

Structure pour gérer les composantes connexes

Les composantes connexes d'un graphe constituent une partition des sommets du graphe. On souhaite implémenter une structure qui permet de gérer la fusion de deux classes de la partition et de savoir si deux éléments sont dans la même classe. Pour cela, il faut choisir un représentant de chaque classe qui permet d'identifier la classe entière. La classe, nommée Partition, devra supporter les opérations suivantes :

- un constructeur qui reçoit en paramètre l'entier n et crée pour chaque sommet x la classe {x}.
- une méthode trouver(x) qui renvoie le représentant de la classe contenant x.
- une méthode unir(x,y) qui fusionne les classes contenant x et y. Les paramètres x et y doivent être dans des classes différentes au moment de l'appel à la fonction.
- une méthode sontConnectes(x,y) qui renvoie vrai si x et y appartiennent à la même classe.

Pour gérer les partitions d'un ensemble, on peut stocker chaque classe comme un arbre enraciné dans lequel chaque nœud contient une référence vers son nœud père. Le représentant de chaque classe est alors le nœud racine de l'arbre correspondant. 

Indication : on peut utiliser un tableau indicé par les entiers de 0 à n-1, et dont la case d'indice x contient le numéro du père de x.

Question 1 - Programmer la classe Partition. On vous fournit un squelette de cette classe. (25/100 lorsque la classe Partition est correctement implémentée).

Les graphes sont définis dans la classe GraphePondere qui utilise la classe Arete.

Question 2 - Programmer la méthode public GraphePondere kruskal() de la classe GraphePondere qui renvoie une forêt couvrante (un arbre par composante connexe) de poids minimum du graphe courant en utilisant l'algorithme de Kruskal.

Indications :
- La classe Arete implémente l'interface Comparable ce qui permet de comparer deux arêtes en comparant leurs poids.
- Vous pouvez utiliser la méthode sort() de la classe Arrays qui trie les éléments d'un tableau.

Fichiers pour le test. On vous fournit les fichiers suivants pour le test :
- test1.txt qui contient le graphe de la maison pondéré. Le poids d'un arbre couvrant de poids min est 6 ;
- test2.txt contient le même graphe mais avec des arêtes de poids 1. La valeur attendue est 4.

Javadoc de GraphePondere.java

Javadoc de Arete.java


Requested files

Executable.java

Loading

maison.txt

Loading

maisonUnitaire.txt

Loading

Arete.java

Loading

GraphePondere.java

Loading

Partition.java

Loading