La représentation des données

On représente toujours les solutions sous forme d'arbre de racine 1.

 

Figure: Exemple de représentation sous forme d'arbre de l'exemple précédent

On utilise des tableaux pour représenter l'arbre. On appelle p(i) le prédécesseur de i. poid(i) est le poids de l'arc entre p(i) et i. sens(i) vaut 0 si l'arc entre p(i) et i est dirigé vers la racine et 1 sinon. Pour notre exemple, cela donne :

i	1	2	3	4	5	6	7
p	/	4	2	1	1	1	2
poid	/	9	6	1	8	9	15
sens	/	0	1	1	1	0	0

Pour avoir plus d'information, on utilise également un tableau d qui donne les profondeurs (hauteurs) des noeuds dans l'arbre. Par exemple :

i	1	2	3	4	5	6	7
d	0	2	3	1	1	1	3

Enfin on appele s(i) le successeur suivant le préordre de i.

i	1	2	3	4	5	6	7
s	6	3	7	2	1	4	5

Remarque
s n'est pas unique.