Class Prim

java.lang.Object
  |
  +--Prim

class Prim

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 Prim.

Field Summary

(package private) java.util.Vector

dessin

Constructor Summary

Prim()
Constructeur par défaut

Method Summary

void	algorithme(Graphe graphe) Application de l'algorithme de Christofidès
(package private) java.util.Vector	arbreRecouvrant(Graphe graphe) Construction des arêtes de l'arbre recouvrant avec l'algorithme de Prim.
(package 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

Prim

public Prim()

Constructeur par défaut

Method Detail

arbreRecouvrant

java.util.Vector arbreRecouvrant(Graphe graphe)

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

Parameters:

graphe - les points du graphe.

Returns:

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

creeDessin

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