Listes de successeurs

  Une façon plus compacte de représenter un graphe consiste à associer à chaque sommet la liste de ses successeurs. Ceci peut se faire, par exemple, à l'aide d'un tableau à double indice que l'on notera . On suppose que les sommets sont numérotés de à , alors pour un sommet et un entier , est le ème successeur de . Cette représentation est utile pour obtenir tous les successeurs d'un sommet . Elle permet d'y accéder en un nombre d'opérations égal au nombre d'éléments de cet ensemble et non pas, comme c'est le cas dans la matrice d'adjacence, au nombre total de sommets. Ainsi si dans un graphe de sommets chaque sommet n'a que successeurs l'obtention de tous les successeurs de se fait en consultant ou valeurs au lieu des tests à effectuer dans le cas des matrices.     L'utilisation d'un symbole supplémentaire noté , signifiant ``indéfini'' et n'appartenant pas à permet une gestion plus facile de la fin de liste. On le place à la suite de tous les successeurs de pour indiquer que l'on a terminé la liste. Ainsi

signifie que est le ème successeur de

signifie que a successeurs.

Le graphe donné figure plus haut admet alors la représentation par liste de successeurs suivante:

Les déclarations Pascal correspondantes peuvent être alors les suivantes:  

    const
        Nmax = 50;   (* Nombre maximal de sommets pour un graphe *)
        MaxDeg = 30; (* Nombre maximal de successeurs pour un sommet *)
        Omega = -1;  (* - *)
    type
        IntSom = 1..Nmax;
        Sommet = integer;
        GrapheSuc = array[IntSom, 1..MaxDeg] of Sommet;
    var
        succ: GrapheSuc;
        n: integer;

Le parcours de la liste des successeurs d'un sommet s'effectue alors à l'aide de la suite d'instructions suivantes , et on retrouvera cette suite d'instructions comme brique de base de beaucoup de constructions d'algorithmes sur les graphes :

    k := 1;
    j := succ[i,k];
    while (j <> Omega) do
        begin
        Traiter(j); (* - *)
        k := k + 1;
        j := succ[i,k];
        end;

On peut transformer la matrice d'adjacence d'un graphe en une structure de liste de successeurs par l'algorithme suivant :

procedure TransformMatSuc (m: GrapheMat; n: integer; var succ: GrapheSuc);
    var
        k: integer;
        i, j: IntSom;
    begin
    for i := 1 to n do
        begin
        k := 1;
        for j := 1 to n do
            if (m[i, j] = 1) then
                begin
                succ[i, k] := j;
                k := k + 1
                end;
            succ[i, k] := Omega
        end;
    end;

Remarque La structure de liste de successeurs peut être remplacée par une structure de liste chaînée faisant intervenir des pointeurs dans le langage Pascal. Cette programmation permet de gagner en place mémoire en évitant de déclarer un nombre de successeurs maximum pour chacun des sommets. Elle permet aussi de diminuer le nombre d'opérations chaque fois que l'on effectue des opérations d'ajout et de suppression de successeurs. Cette notion peut être omise en première lecture, en particulier par ceux qui ne se sentent pas très à l'aise dans le maniement des pointeurs. Dans toute la suite, les algorithmes sont écrits avec la structure matricielle Succ[x,i]. Un simple jeu de traduction permettrait de les transformer en programmation par pointeurs; on utilise les structures de données suivantes : 

type
    ListeSom = ^SomCell;
    SomCell = record
        val: Sommet;
        suiv: ListeSom;
        end;
    GraphePoint = array[IntSom] of ListeSom;

La transformation de la forme matricielle en une structure de liste chaînée par des pointeurs se fait par l'algorithme donné ci dessous, on peut noter que celui-ci inverse l'ordre dans lequel ont rangés les successeurs d'un sommet, ceci n'a pas d'importance dans la plupart des cas:

procedure TransformSucPoint (succ: GrapheSuc; n: integer; 
                             var gpoint: GraphePoint);
    var
        i: integer;
        x: Sommet;
        s: ListeSom;
    begin
    for x := 1 to n do
        begin
        gpoint[x] := nil;
        i := 1;
        while (succ[x, i] <> Omega) do
            begin
            new(s);
            s^.val := succ[x, i];
            s^.suiv := gpoint[x];
            gpoint[x] := s;
            i := i + 1;
            end;
        end;
end;