L'ALGORITHME DE KRUSKAL

 

PRINCIPE:

Données:

Un graphe composé de N sommets est donné par la liste de ses arêtes dans l'ordre de leur poids croissant.
Soit
T l’arbre recherché.

Méthode:

La liste des arêtes est lue en commençant par l'arête de plus faible poids, notée u1.
Au départ
T = {u1}.
A l'étape
k l'arête uk est lue. Si elle ne forme pas de cycle avec les arêtes de T alors elle est retenue.
L’algorithme s’arrête quand le nombre d’arêtes de
T est égal à N-1.

 


 

ALGORITHME:

Soit
G=(X,U) avec |X| =N et |U|= M.

1) Classer les arêtes par ordre de longueur croissante
(u1, u2, u3,....,uM)

2) T=Æ , i=1

3) Si T+ui est sans cycle ajouter ui à T.
T ß T + {u1}
Sinon aller en 4.

4) Incrémenter i de 1.
Si
|T| = N-1 Stop, sinon retourner en 3.

Retour en haut de page