Création d'un graphique à l'aide d'une liste d'adjacence

Question

Je suis en train de suivre le Manuel de conception d'algorithmes de Skiena v3.

J'ai vu quelques questions indiquant qu'il y a certaines coquilles dans le livre, et je ne suis pas sûr s'il s'agit de l'une d'entre elles ou simplement parce que je ne peux pas le comprendre.

Considérez ce qui suit:

typedef struct edgenode {
    int y;                   /* info d'adjacence */
    int weight;              /* poids de l'arête, le cas échéant */
    struct edgenode *next;   /* arête suivante dans la liste */
} edgenode;

typedef struct {
    edgenode *edges[MAXV+1];  /* info d'adjacence */
    int degree[MAXV+1];       /* nombre de arcs sortants de chaque sommet */
    int nvertices;            /* nombre de sommets dans le graphe */
    int nedges;               /* nombre d'arêtes dans le graphe */
    int directed;             /* le graphe est-il dirigé ? */
} graph;

void insert_edge(graph *g, int x, int y, bool directed) {
    edgenode *p;        /* pointeur temporaire */

    p = malloc(sizeof(edgenode));    /* allocation du stockage edgenode */

    p->weight = 0;
    p->y = y;
    p->next = g->edges[x];

    g->edges[x] = p;    /* insertion en tête de la liste */

    g->degree[x]++;

    if (!directed) {
        insert_edge(g, y, x, true);
    } else {
        g->nedges++;
    }
}

D'après ce que je comprends, void insert_edge(graph *g, int x, int y, bool directed) connecte deux nœuds à l'index du tableau x et y en les ajoutant au tableau edges.

L'extrait suivant me confond:

p->y = y;
p->next = g->edges[x];

g->edges[x] = p;    /* insert at head of list */

Comment cela fonctionne-t-il? Supposons que mon entrée soit x = 3, y = 4, et que c'est la première entrée.

Je m'attendrais à quelque chose comme 3 -> 4 pour un graphe dirigé.

1. p->y = y; a tout son sens, l'adjacence de x est y.
2. p->next = g->edges[x]; Mais le tableau edges est initialisé à null. Cela ne fera-t-il pas que 3.next == NULL au lieu de 3.next == 4 ?
3. g->edges[x] = p; Quoi? edges[x] == x Node, cela me perturbe.

Le code complet peut être trouvé sur graph.c et graph.h.

Je pense que p.next = y; d'une certaine manière et y.next = NULL pour le moment c'est-à-dire la première insertion. Peut-être que c'est à cause de mon C rouillé mais j'ai besoin d'aide sur ce point.

Answer 1

D'après ce que je comprends, insert_edge connecte deux nœuds aux indices du tableau x et y en les ajoutant au tableau edges.

Je ne qualifierais pas cela de "ajout au tableau edges", car le tableau edges a une longueur fixe et possède une entrée pour chaque nœud (et non pour chaque arête).

L'index de edges identifie le sommet "départ" d'une arête et le champ y d'un edgenode identifie le sommet "arrivée" correspondant de la même arête.

Pour chaque sommet x, ce code maintient une liste chaînée d'arêtes (pas du tableau edges, mais de edges[x]), qui sera initialement vide.

Passons à un exemple de graphe :

...qui, après initialisation, est peuplé avec ses arêtes comme suit :

insert_edge(g, 0, 1, true); 
insert_edge(g, 0, 2, true); 
insert_edge(g, 1, 2, true); 
insert_edge(g, 2, 3, true); 
insert_edge(g, 3, 4, true); 

Observons comment cela peuple la structure de données graph. Nous commençons avec cet état pour g (où je suppose que MAXV est 4 pour cette représentation) :

g  edges       -   -   -   -   - 

     degree      0   0   0   0   0 

     nvertices   5  

     nedges      0 

     directed  true

Les tirets représentent des valeurs de nullpointer. Je suppose que tout ceci a été correctement initialisé.

Ensuite, insert_edge(g, 0, 1, true) va créer un nœud p, qui est alloué et initialisé comme ceci :

p  weight   0 

     y        1 

     next     - 

Notablement, le champ next est nullptr, car c'est la valeur située à g->edges[0].

Ensuite l'instruction suivante g->edges[x] = p fait le lien, et après que deux compteurs aient été incrémentés, la fonction a terminé son travail :

                  p  weight   0 

                       y        1 

                    next     - 

g  edges          -   -   -   - 

     degree      1   0   0   0   0 

     nvertices   5  

     nedges      1 

     directed  true

Passons à un cas plus intéressant : insert_edge(g, 0, 2, true);. Encore une fois, p est pointé vers un nouveau edgenode, mais cette fois-ci g->edges[0] n'est pas nullptr et donc p->next va pointer vers le edgenode ajouté précédemment. Après que insert_edge ait terminé, nous obtenons ceci :

                  p  weight   0    weight   0 

                       y        2    y        1 

                    next      next     - 

g  edges          -   -   -   - 

     degree      2   0   0   0   0 

     nvertices   5  

     nedges      2 

     directed  true

Et ainsi de suite pour les autres arêtes : à chaque fois que le nouveau edgenode est ajouté en tête d'une liste chaînée dont le pointeur de tête est stocké dans le tableau edges. Nous avons 5 listes chaînées : une pour chaque sommet.

Voici le résultat final pour l'exemple ci-dessus :

                       weight   0    weight   0 

                       y        2    y        1 

                    next      next     - 

                           weight   0    weight   0 

                           y        4    y        2 

                        next      next     - 

                               weight   0 

                               y        3 

                            next     - 

                                   weight   0 

                                   y        4 

                                next     - 

g  edges                   - 

     degree      2   2   1   1   0 

     nvertices   5  

     nedges      6 

     directed  true

J'espère que cela clarifie les choses.