On considérera deux principales méthodes de représentation des graphes : les matrices et les listes de connectivité. Le choix entre elles se fera en fonction de la densité du graphe.
Pour ces deux méthodes, il faut pouvoir faire correspondre au nom d'un sommet une valeur entière unique entre 1 et NbSommets. Ceci afin d'accélérer l'accès à l'information propre à un sommet :
Pour simplifier, nous considérerons dans les exemples qui suivent des sommets dont les noms sont formés d'un seul caractère. Ainsi, à la i-ème lettre de l'alphabet, l'on fera correspondre l'entier i.
Une matrice de valeurs booléennes (Relie) de dimension NbSommets * NbSommets indique qu'il y a un arc entre un sommet x et un sommet y si Relie[x,y] est vrai. Il est à remarquer que chaque arc est représenté deux fois (Relie[x,y] et Relie[y,x]). On peut ainsi, pour un graphe non-orienté, économiser de l'espace en ne stockant que le triangle supérieur de la matrice symétrique.
Cette méthode de représentation est indiquée si le graphe est dense car il faut NbSommets2 booléens pour stocker le graphe et NbSommets2 étapes pour initialiser la matrice. Par densité, on entend la proportion d'arcs effectifs par rapport au nombre maximum d'arcs possibles (NbArcs / NbSommets2).
Pour le graphe que nous avons déjà vu auparavant dans la figure 10.1, la matrice de connectivité (Relie) correspondante est donnée par la figure 10.2.
A B C D E F G H I J K L M A f v v f f v v f f f f f f B v f f f f f f f f f f f f C v f f f f f f f f f f f f D f f f f v v f f f f f f f E f f f v f v v f f f f f f F v f f v v f f f f f f f f G v f f f v f f f f f f f f H f f f f f f f f v f f f f I f f f f f f f v f f f f f J f f f f f f f f f f v v v K f f f f f f f f f v f f f L f f f f f f f f f v f f v M f f f f f f f f f v f v f
Fig. 10.2. Matrice de connectivité.
Cette matrice peut être construite à l'aide de l'algorithme suivant
program MatriceGraphe;
const MaxNbSommets = ...;
type UnSommet = ...;
var j, x, y, NbSommets, NbArcs : integer;
Sommet1, Sommet2: UnSommet;
Relie : array[1..MaxNbSommets, 1..MaxNbSommets] of boolean;
Sommets : array[1..MaxNbSommets] of UnSommet;
function Index(Sommet: UnSommet):integer;
{ fonction qui associe une valeur numérique entière
à un objet de type "UnSommet" et qui stocke le "Sommet"
dans le tableau "Sommets" si ce sommet ne s'y trouvait pas déjà. }
begin
...
end; { Index }
begin { MatriceGraphe }
{ lecture du nombre de données }
readln(NbSommets,NbArcs);
{ initialisation de la matrice }
for x := 1 to NbSommets do
for y := 1 to NbSommets do
Relie[x,y] := false;
for j := 1 to NbArcs do begin
{ pour chaque arc, on lit les sommets
de départ et d'arrivée }
readln (Sommet1,Sommet2);
x := Index (Sommet1);
y := Index (Sommet2);
{ crée un arc dans chaque direction }
Relie[x,y] := true;
Relie[y,x] := true;
end; { for }
end. { MatriceGraphe }
Si le graphe n'est pas dense, on peut opter pour un autre mode de représentation : celui de listes de connectivité (il s'agit en fait de chaînes) dont les éléments sont de la forme :
type Ref = ^Noeud;
Noeud = record
IndexVoisin : integer;
Suivant : Ref;
end; { Noeud }
Un vecteur de NbSommets composantes contient les pointeurs de tête de chaque liste :
L'algorithme de lecture et de construction de cette structure est le suivant :
program ChaineGraphe;
const MaxNbSommets = ... ;
type UnSommet = ...;
Ref = ^Noeud;
Noeud = record
IndexVoisin : integer;
Suivant : Ref;
end; { Noeud }
var j, x, y, NbSommets, NbArcs: integer;
Voisin: Ref;
Sommet1, Sommet2: UnSommet;
PremierVoisin: array[1..MaxNbSommets] of Ref;
Sommets : array[1..MaxNbSommets] of UnSommet;
function Index(Sommet: UnSommet): integer;
begin
...
end; { Index }
begin
{ lecture du nombre de données }
readln (NbSommets, NbArcs);
{ initialisation }
for j := 1 to NbSommets do
PremierVoisin[j] := nil;
{ pour chaque arc lit sommet de départ
et d'arrivée }
for j := 1 to NbArcs do begin
readln (Sommet1,Sommet2);
x := Index (Sommet1);
y := Index (Sommet2);
{ crée l'arc de y vers x }
new(Voisin);
Voisin^.IndexVoisin := x;
Voisin^.Suivant := PremierVoisin[y];
PremierVoisin[y] := Voisin;
{ crée l'arc de x vers y }
new(Voisin);
Voisin^.IndexVoisin := y;
Voisin^.Suivant := PremierVoisin[x];
PremierVoisin[x] := Voisin;
end; { for }
end. { ChaineGraphe }
Ce qui produit dans notre exemple la structure de données suivante :
Fig. 10.4. Listes de connectivité correspondant au graphe de la figure 10.1.
A noter que les arcs apparaissent deux fois. Par exemple B se trouve dans la liste de connectivité de A et A se trouve dans la liste de connectivité de B.
Si le langage utilisé admet les structures paquetées, l'occupation mémoire d'une matrice de connectivité est inférieure à l'occupation mémoire de la liste de connectivité correspondante dès que la densité des arcs dépasse 3%. En effet, il faut 1 bit par arc pour une matrice de connectivité et généralement 32 bits par arc pour la liste de connectivité correspondante (1 pointeur+1 numéro de sommet).
En fait, ici, c'est plus le nombre d'étapes d'initialisation et de traitement que l'occupation en mémoire qu'il faut prendre en considération pour choisir entre les deux types de structures. La structure de liste nécessite moins d'étapes d'initialisation et de traitement mais cet avantage devient de moins en moins déterminant au fur et à mesure que la densité des arcs augmente. Il y a donc un compromis à trouver entre gain de temps et gain de place.
L'utilisation de listes présente une particularité que la matrice de connectivité n'avait pas; en effet, ce qui caractérise une chaîne de connectivité, c'est l'ordre dans lequel les éléments apparaissent dans la liste. Par conséquent, quel que soit l'ordre des éléments, donc quelle que soit la façon dont on voit le graphe, il faut que les algorithmes qui manipulent ces représentations produisent des résultats équivalents.
Des opérations simples ne sont pas simplement réalisables sur ce type de représentation. Par exemple l'élimination d'un sommet doit se faire dans toutes les listes. On peut partiellement y remédier en rajoutant à chaque élément de la liste de connectivité d'un sommet un pointeur vers l'élément d'une autre liste de connectivité qui décrit le même arc. Par exemple, l'élément référençant B dans la liste de connectivité de A aura un pointeur vers l'élément référençant A de la liste de connectivité de B car, dans les deux cas, il s'agit de l'arc AB :
Les deux types de représentation de graphes vus précédemment sont les plus couramment utilisés. En effet, même si l'on ne connaît pas à l'avance le nombre de sommets d'un graphe, la plupart des langages de programmation offrent la possibilité de déclarer des tableaux conformants (tableaux dont les bornes d'indices ne sont pas fixées à la compilation). Il est ainsi possible d'ajuster la taille de la structure statique (matrice de booléens ou tableau de pointeurs) en fonction des données du problème. Cela ne permet cependant pas d'augmenter facilement le nombre de sommets en cours d'exécution si cela s'avérait nécessaire pour les besoins de l'application.
L'on peut toutefois envisager d'utiliser une structure entièrement dynamique en créant une chaîne décrivant les sommets du graphe, où chaque élément contiendrait le nom d'un sommet, un pointeur vers le sommet suivant (dans l'ordre alphabétique, par exemple) ainsi qu'un pointeur vers une chaîne décrivant les arcs partant de ce sommet. On aurait ainsi une chaîne des sommets et, pour chaque élément de cette chaîne, une chaîne des arcs. Cela pourrait donner la structure suivante :
Cet exemple indique qu'il y a deux arcs partant du sommet Nom1, (dont un vers Nom2), trois arcs partant de Nom2, ... et un arc partant de NomN. Cette structure peut être construite à l'aide des déclarations et de l'algorithme suivants :
type VersSommet = ^Sommets;
VersArc = ^Arcs;
Sommets = record
Nom: string;
PremierArc: VersArc;
SommetSuivant: VersSommet;
end; { Sommets }
Arcs = record
PointeVers: VersSommet;
ArcSuivant: VersArc;
end; { Arcs }
var Graphe: VersSommet;
procedure LireSommet;
var Nom: string; P:VersSommet;
begin
read(Nom);
while Nom <> 'FIN' do begin
new(P);
P^.Nom := Nom;
P^.PremierArc := nil;
P^.SommetSuivant := Graphe;
Graphe := P;
readln; read(Nom);
end; { while }
readln;
end; { LireSommet}
procedure LireArcs;
var Dep, Arr: VersSommet;
A: VersArc;
Depart, Arrivee: string;
begin
while not eof(input) do begin
readln(Depart, Arrivee);
{ recherche des 2 sommets dans la
chaîne des sommets }
P := Graphe;
Arr := nil;
Dep := nil;
repeat
if P = nil then Erreur
else if P^.Nom = Depart then Dep:=P
else if P^.Nom=Arrivee then Arr:=P;
P := P^.SommetSuivant
until (Arr <> nil) and (Dep <> nil);
new(A);
A^.PointeVers := Arr;
A^.ArcSuivant := Dep^.PremierArc;
Dep^.PremierArc := A;
end; { while }
end; { LireArcs }
Au besoin, il est possible de remplacer, dans l'exemple qui précède, la chaîne des sommets par un arbre binaire de tri. Les sommets deviennent ainsi plus rapidement localisables, au cas où l'on désire y accéder sans passer par un arc.
10.3. Recherche
en profondeur
Site Hosting: Bronco
Table des
matières.