Matrice et listes : les deux conversions

#define N_MAX 100
#define DEG_MAX 50
int m[N_MAX][N_MAX];
int voisins[N_MAX][DEG_MAX + 1];    /* voisins[u][0] = nombre de voisins de u */

/* Remplit voisins à partir de m. Précondition : n <= N_MAX et tout sommet a
   au plus DEG_MAX voisins sortants. Complexité : Theta(n^2). */
void listes_de_matrice(int n) {
    assert(0 < n && n <= N_MAX);
    for (int u = 0; u < n; u = u + 1) {
        voisins[u][0] = 0;
        for (int v = 0; v < n; v = v + 1) {
            if (m[u][v] == 1) {
                assert(voisins[u][0] < DEG_MAX);
                voisins[u][0] = voisins[u][0] + 1;
                voisins[u][voisins[u][0]] = v;
            }
        }
    }
}

/* Remplit m à partir de voisins. Complexité : Theta(n^2 + m). */
void matrice_de_listes(int n) {
    assert(0 < n && n <= N_MAX);
    for (int u = 0; u < n; u = u + 1) {
        for (int v = 0; v < n; v = v + 1) { m[u][v] = 0; }   /* Theta(n^2) */
    }
    for (int u = 0; u < n; u = u + 1) {
        for (int k = 1; k <= voisins[u][0]; k = k + 1) {     /* Theta(m) */
            m[u][voisins[u][k]] = 1;
        }
    }
}

Mesuré sur le graphe du chapitre : voisins[0] vaut $\{2;1,2\}$, voisins[1] vaut $\{1;3\}$, voisins[2] vaut $\{0;\}$ et voisins[3] vaut $\{1;2\}$, et l'aller-retour redonne la matrice de départ à l'identique.

Ce que les complexités révèlent, et c'est tout l'intérêt de l'exercice.

• Matrice $\to$ listes coûte $\Theta (n^2)$, et non $\Theta (n+m)$ : il faut lire toutes les cases pour découvrir les arcs, y compris les $n^2-m$ cases nulles. Une matrice ne se lit pas plus vite que sa taille, même si le graphe est creux. C'est exactement la ligne « parcourir tous les arcs » du tableau du chapitre.
• Listes $\to$ matrice coûte $\Theta (n^2+m)=\Theta (n^2)$, dominé par l'initialisation à zéro. Il faut écrire toutes les cases, même celles qui resteront nulles.

La conséquence pratique : convertir vers la matrice est aussi coûteux que de travailler avec elle. Sur un graphe creux, la conversion n'est jamais rentable — si l'on a besoin d'un test d'arc en $O(1)$, on ajoute une table de hachage des couples plutôt qu'une matrice, et l'on reste en $\Theta (n+m)$ de mémoire.

Un détail de sûreté : assert(voisins[u][0] < DEG_MAX) est indispensable. Sans lui, un sommet de degré supérieur à DEG_MAX écrirait dans la ligne suivante du tableau à deux dimensions — les lignes sont contiguës en mémoire —, corrompant les voisins d'un autre sommet sans le moindre message. C'est le débordement de tampon du chapitre chap:langage-c, dans un décor de graphes.