TP 4 - Algorithme de Kruskal

L'objectif de ce TP est d'implémenter l'algorithme de Kruskal.

Exercice 1

Modifier le module de gestion des graphes pour qu'il gère les graphes non orientés avec arêtes pondérées

Exercice 2

Qu'est qu'une forêt couvrante de poids minimal?

On considère le graphe non orienté valué G suivant:

Un graphe orienté
Figure 1 - Un graphe orienté

Déterminer un arbre recouvrant de G de poids minimum depuis le sommet s_{\mathfrak{0}} en utilisant l'algorithme de Kruskal.

Rappel:

KRUSKAL(G)
    E = {}
    pour chaque sommet v de G faire
        CREER_ENSEMBLE( v )
    trier les arêtes de G par ordre croissant de poids w
    pour chaque arête (u,v) de G pris par ordre de poids croissant faire
        si TROUVER_ENSEMBLE(u) <> TROUVER_ENSEMBLE( v )
            E = E + { (u,v) }
            FUSIONNER_ENSEMBLE( u,v )
    retourner E

Implémenter l'algorithme de Kruskal.

Ce TP est inspiré du TP TD 4 et des TDs donnés au Licences Informatiques INF351 de l'Université Bordeaux 1.