Class Kruskal

java.lang.Object
  |
  +--Kruskal

public class Kruskal

extends java.lang.Object

implements Algorithme

Construit une approche du problème du voyageur de commerce à l'aide de l'heuristique de Christofidès. L'arbre recouvrant minimal est constuit par l'algorithme de Kruskal.

Field Summary

(package private) java.util.Vector

dessin

Constructor Summary

Kruskal()
Constructeur par défaut

Method Summary

void	algorithme(Graphe graphe) Application de l'algorithme de Christofidès
private java.util.Vector	arbreRecouvrant(Graphe graphe) Construction des arêtes de l'arbre recouvrant avec l'algorithme de Kruskal.
private void	creeDessin(Graphe graphe, java.util.Vector circuit) Crée le tableau contenant les informations nécessaires à la construction du dessin

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait

Field Detail

dessin

java.util.Vector dessin

Constructor Detail

Kruskal

public Kruskal()

Constructeur par défaut

Method Detail

arbreRecouvrant

private java.util.Vector arbreRecouvrant(Graphe graphe)

Construction des arêtes de l'arbre recouvrant avec l'algorithme de Kruskal.

Parameters:

graphe - contient les informations sur les points et les distances entre les points.

Returns:

le tableau des arêtes de l'arbre recouvrant.

creeDessin

private void creeDessin(Graphe graphe,
                        java.util.Vector circuit)

Crée le tableau contenant les informations nécessaires à la construction du dessin

Parameters:

graphe - les informations sur le graphe

circuit - l'approche du problème du voyageur de commerce sur le graphe

algorithme

public void algorithme(Graphe graphe)

Application de l'algorithme de Christofidès

Specified by:

algorithme in interface Algorithme

Parameters:

graphe - les informations sur le graphe