Informatique -- Tronc Commun
TD 8 - Graphes: algorithme de Kruskal

Benjamin Werner, Eric Schost

3 janvier 2000

Meilleurs voeux pour l'année 2000 !

Objet

On va aujourd'hui manipuler des graphes. C'est un peu plus complexes que les arbres, car on ne peut pas ``tenir'' un graphe par un seul bout, comme on tient un arbre par sa racine.

Aujourd'hui, on représente un graphe par le tableau des arêtes. Chaque arêtes est décrite par trois entiers: les numéros de ses deux sommets, et son ``poids''.

On peut comprendre le poids d'une arête comme une mesure de longueur.

1 L'algorithme

Le but du TD est de construire un arbre tel que:

Tous les sommets du graphe font partie de l'arbre,
chaque branche de l'arbre est une arête du graphe,
la somme des poids des branches de l'arbre est minimale.

L'algorithme choisi est du à Kruskal. Son principe est assez simple et repose sur les remarques suivantes:

L'arbre recherché peut être vu comme une partie des arêtes du graphe de départ.
A l'inverse, une partie de l'ensemble des arêtes, qui ne contient pas de cycle, décrit un sensemble d'arbres (``une forêt''); quand on joute une arête sans créer de cycle, on a toujours une forêt.
Quand on a ajouté n-1 arêtes (n étant le nombre de sommets), tous les sommets sont connectés, et on a construit un arbre recouvrant le graphe.

L'algorithme procède donc comme suit. On part d'un ensemble vide d'arrêtes. A chaque étape, on ajoute l'arête de plus faible poids qui ne crée pas de cycle. On s'arrete quand:

après n-1 étapes; on a alors fini.
s'il n'y a plus d'arêtes; cela veut dire que l'on est parti d'un graphe non-connexe.

Il faut travailler un peu pour prouver que le résultat est bien un arbre de poids minimal. Mais ce n'est pas l'objet du TD.

2 Détection de cycles

A chaque étape, il faut vérifier si l'on crée un cycle en rajoutant une arrête à l'ensemble courant (la forêt courante). Pour cela, une bonne manière est de représenter la forêt comme un tableau d'entiers, où t[a] est l'indice du ``père'' du sommet d'indice a. Bien sûr, il faut choisir une valeur par défaut, comme t[a]=-1 pour indiquer que le sommet a n'a pas (encore) de père.

A partir de là, il est facile de verifier si l'arête (a,b) ajoute un cycle. Il siffit de vérifier si a et b font partie du même arbre: Il suffit de calculer leurs racines respectives i et j et de les comparer.

Si i est différent de j, on ajoute alors l'arête (a,b) en faisant soit t[i]=j, soit t[j]=i.

3 Travail

J'ai essayé de bien baliser le travail. Comme dit plus haut, une arête est un triplet d'entier. Une définition possible est donc:

class Arete {
    int g,d,p ;
    Arete(int g, int d, int p) {
        this.g=g; this.d=d; this.p=p; }
}

Le plus simple est de travailler à partir du fichier Kruskal.java où vous trouverez d'autres explications.

Il s'agit de finir le programme, et de l'essayer à partir d'un petit graphe entré au clavier.

Vous pouvez ajouter de nouvelles fonctions si cela vous parait plus simple. L'astuce essentielle est la fonction cyclep qui teste si deux sommets sont déja connectés et ajoute une arête si ce n'est pas le cas.

Une solution se trouve ici.

4 Affichage

Pour afficher joliment un arbre, rien ne vaut une représentation à base de pointeurs. Une représentation à base de pointeurs d'arbres arbitrairement branchant peut être:

class Arbre {
    int indice;
    Foret suiv;
    Arbre (int i, Foret f){
        indice = i; suiv = f; }
}

class Foret {  // une liste d'arbres
    Arbre prem;
    Foret reste;
    Foret (Arbre a, Foret f){
        prem = a;
        reste = f; }
}

Remarquez que ces deux classes sont récursives et dépendent mutuellement l'une de l'autre.

Il faut donc traduire un tableau en Arbre, puis l'afficher graphiquement.

Vous pouvez partir du fichier suivant: Arbre.java qui propose une fonction d'affichage sommaire.

This document was translated from L^AT_EX by H^EV^EA.

Informatique -- Tronc CommunTD 8 - Graphes: algorithme de Kruskal