STRUCTURES ARBORESCENTES

  Un arbre est un ensemble de noeuds, organisés de façon hierarchique,
à partir d'un noeud distingué, appelé racine. La structure d'arbre
est l'une des plus importantes et des plus spécifiques de l'informatique :
par exemple, c'est sous forme d'arbre que sont organisés les fichiers
dans des systèmes d'exploitation tels que UNIX ou MULTICS; c'est aussi
sous forme d'arbres que sont représentés les programmes traités par
un compilateur.
  Une propriété intrinsèque de la structure d'arbre est la récursivité,
et les définitions des caractéristiques des arbres, aussi bien que les
algorithmes qui manipulent des arbres s'écrivent très naturellement de
manière récursive.


GRAPHES

  Beaucoup de problèmes de la vie courante, tels la gestion de réseaux
de communication ou l'ordonnancement de tâches, correspondent à des
structures relationnelles que l'on peut modéliser par des graphes.
Informellement un graphe est un ensemble d'objets, appelés sommets,
et de relations entre ces sommets.

Représentation des graphes
  On peut représenter les graphes de plusieurs manières. On peut
distinguer deux grandes classes de représentations, selon que l'on
privilégie le fait qu'un graphe est un ensemble d'arcs (resp. arêtes)
ou un ensemble de sommets.

Utilisation de matrices
  Cette représentation correspond au cas où l'ensemble des sommets du
graphe n'évolue pas; on représente l'ensemble des arcs par un tableau
de booléens; comme chaque arc est une paire ordonnée de sommets, le
graphe est représenté par une matrice carrée de booléens, dite matrice
d'adjacence, de dimensions nxn si le graphe a n sommets.
On a donc le type Pascal suivant :
  type GRAPHE=array[1..n,1..n] of boolean;

Utilisation de listes d'adjacence
  Une autre représentation classique des graphes consiste à représenter
l'ensemble des sommets et à associer à chaque sommet la liste de ses
successeurs rangés dans un certain ordre. Les listes sont appelées
listes d'adjacences. Dans le cas où l'ensemble des sommets n'évolue
pas, ces listes sont accessibles à partir d'un tableau S, qui contient
pour chaque sommet, un pointeur vers le début de la liste.
  type adr=^doublet;
    doublet=record no:1..n; suiv:adr end;
    GRAPHE=array[1..n] of adr;