Les graphes : représenter et parcourir

Toutes les structures vues jusqu'ici imposaient la même contrainte : un élément, un voisin de chaque côté. Le graphe la lève, et c'est la seule chose qu'il fait. Tout le reste — les deux façons de le ranger en mémoire, les deux façons de le parcourir — découle de cette levée.

Quand un seul voisin ne suffit plus

Le module Les structures linéaires se termine sur une phrase qui appelle celui-ci : « chaque élément a au plus un voisin de chaque côté ». C'est cette contrainte qui donnait aux cinq structures leur forme, et c'est elle qui les limitait. Une file d'attente n'a qu'un suivant. Une liste doublement chaînée en a deux, un devant et un derrière, et pas un de plus.

Un graphe est ce qu'on obtient quand on retire cette contrainte, et rien d'autre. Un élément peut avoir zéro voisin, ou dix-sept ; deux éléments peuvent se pointer mutuellement ; on peut partir d'un élément, suivre des voisins, et revenir à son point de départ. La liste chaînée devient d'ailleurs un cas particulier de graphe — celui où chacun a exactement un voisin.

Ce que ça permet de modéliser est vaste, et la liste vaut d'être lue en entier une fois, parce que c'est elle qui explique pourquoi ce chapitre pèse trois semaines dans la session.

• Le métro : les stations, et les segments qui les relient. « Comment aller d'Université-de-Montréal à Berri-UQAM ? » est une question de graphe, et tu la résous mentalement chaque fois que tu regardes le plan.
• Un réseau social : les personnes, et les liens d'amitié ou d'abonnement.
• Un cursus universitaire : les cours, et les préalables. IFT-2008 exige IFT-1006, qui exige autre chose : c'est un graphe, et l'ordre dans lequel on peut suivre ses cours en est une propriété calculable.
• Le web : les pages, et les hyperliens. Le classement de Google a commencé par un calcul sur ce graphe-là.
• Un réseau routier ou aérien : les villes, et les trajets. C'est exactement le sujet du deuxième travail pratique du cours.

Sommet, arête, arc : le vocabulaire qui sert

Le vocabulaire des graphes est court, et il vaut la peine de le poser proprement une fois : il sert d'une part à lire les énoncés d'examen, qui l'emploient sans le redéfinir, et d'autre part à énoncer les complexités, qui parlent toutes de deux nombres seulement.

Un graphe se note G = (V, E) — deux ensembles. V pour vertices, les sommets : les points, les nœuds, les stations. E pour edges, les liens entre ces sommets. On note n = |V| le nombre de sommets et m = |E| le nombre de liens, et ces deux lettres sont celles dans lesquelles toutes les complexités du chapitre s'écriront.

Reste le mot le plus important, et c'est celui qui distingue les deux sortes de liens. Un lien peut être réciproque ou à sens unique, et le français a deux mots pour ça : une arête est réciproque, un arc est orienté. La distinction n'est pas cosmétique — elle change ce que le code stocke, ce que les algorithmes calculent, et elle est la source d'erreur numéro un dans les exercices de graphes.

Deux relations valent d'être retenues, parce qu'elles servent de garde-fou quand on compte. La première : dans un graphe non orienté, chaque arête ajoute 1 au degré de ses deux extrémités, donc la somme de tous les degrés vaut deux fois le nombre d'arêtes.

La seconde borne le nombre d'arêtes. Dans un graphe non orienté sans boucle ni arête répétée, chaque paire de sommets distincts porte au plus une arête, et il y a n(n − 1) / 2 paires possibles.

Retiens surtout l'ordre de grandeur qui s'en déduit : m est au plus de l'ordre de n². C'est ce plafond qui rendra la section « Dense ou creux » décidable au lieu d'être une affaire de goût.

Orienté, non orienté, pondéré

Trois adjectifs qualifient un graphe, et chacun change quelque chose de concret dans le code. Ils sont indépendants : un graphe peut être orienté et pondéré, non orienté et non pondéré, et toutes les combinaisons existent.

Non orienté : la relation est symétrique par nature. « Alice est amie avec Bob » dit exactement la même chose que « Bob est ami avec Alice ». Les liens sont des arêtes. Le métro, un réseau routier à double sens, Facebook.

Orienté : la relation a un sens, et l'inverse n'est pas garanti. « Alice suit Bob » n'implique rien sur ce que fait Bob. Les liens sont des arcs. Les préalables de cours, les hyperliens du web, les rues à sens unique, Instagram.

Pondéré : chaque lien porte un nombre — une distance, une durée, un prix, un risque. Sans pondération, le seul coût d'un chemin est son nombre de liens ; avec, c'est la somme des poids. Ce module travaille exclusivement sur des graphes non pondérés, et c'est le module suivant qui paiera le prix de la pondération.

voisins[0] = {1, 2};
voisins[1] = {0};
voisins[2] = {0};

La matrice d'adjacence

Il n'existe que deux façons de ranger un graphe en mémoire, et le reste du chapitre — y compris toutes ses complexités — dépend de laquelle on choisit. Prenons un graphe de référence, qui servira jusqu'à la fin du module.

Six sommets, nommés A à F. Sept arcs, tous orientés : A→B, A→D, B→C, B→E, C→F, D→E, E→F. Lis-les une fois attentivement, parce que chaque trace de ce module s'y réfère. Si tu veux les visualiser : A, B, C forment une rangée qui va vers la droite, D, E, F une seconde rangée en dessous, et trois arcs descendent de la première vers la seconde.

La matrice d'adjacence est la représentation naïve, au bon sens du terme : un tableau carré de n × n cases, où la case en ligne u et colonne v répond à une seule question — l'arc de u vers v existe-t-il ? On y met 1 pour oui, 0 pour non.

const int N = 6;                 // A..F, donc les indices 0 à 5

// int matrice[N][N] — un tableau à DEUX indices : N lignes de N entiers,
//                     posées les unes après les autres en mémoire.
// = {}              — l'initialisation par accolades VIDES met toutes les
//                     cases à zéro. Sans elle, un tableau local contient
//                     n'importe quoi, et le graphe serait aléatoire.
int matrice[N][N] = {};

matrice[0][1] = 1;   // A -> B
matrice[0][3] = 1;   // A -> D
matrice[1][2] = 1;   // B -> C
// ... les quatre autres arcs

Les sommets sont nommés A à F dans la prose et numérotés 0 à 5 dans le code : un tableau s'indexe par des entiers. C'est la traduction qu'on fait de tête tout du long.

Ce que cette forme achète est immédiat : répondre à « l'arc (u, v) existe-t-il ? » coûte Θ(1). On calcule l'adresse d'une case et on la lit, exactement comme pour un tableau ordinaire — le module Les structures linéaires a détaillé pourquoi ce calcul ne dépend pas de la taille.

Ce qu'elle vend l'est tout autant : elle occupe Θ(n²) de mémoire quel que soit le nombre d'arcs. Un graphe à six sommets et sept arcs remplit trente-six cases dont vingt-neuf valent zéro. Et une conséquence moins visible en découle, qui coûtera plus cher que la mémoire : pour énumérer les voisins de u, il faut parcourir toute la ligne u, soit n cases, même si u n'a qu'un seul voisin.

La liste d'adjacence

L'autre représentation part du constat inverse : la plupart des cases d'une matrice valent zéro, alors ne les stockons pas. Pour chaque sommet, on garde seulement la liste de ses voisins. Six listes au lieu de trente-six cases.

Le type qui porte ça en C++ est celui qu'emploie le travail pratique du cours, et il mérite d'être démonté avant d'être lu, parce qu'il empile trois idées en une ligne.

// vector<int>          — un tableau dynamique d'entiers : la liste des
//                        voisins d'UN sommet.
// vector<vector<int>> — un tableau dynamique DE CES LISTES. Le type entre
//                        chevrons est lui-même un vector : c'est
//                        l'imbrication qui rend la ligne difficile à lire,
//                        pas les chevrons eux-mêmes.
// voisins(N)           — le constructeur avec une taille : on crée
//                        d'emblée N listes, toutes vides.
vector<vector<int>> voisins(N);

voisins[0] = {1, 3};    // A -> B, D
voisins[1] = {2, 4};    // B -> C, E
voisins[2] = {5};       // C -> F
voisins[3] = {4};       // D -> E
voisins[4] = {5};       // E -> F
// voisins[5] reste vide : F n'a aucun arc sortant

voisins[u] se lit « la liste des voisins sortants de u », et voisins[u][i] « le i-ième d'entre eux ». Deux crochets successifs, deux niveaux d'imbrication.

Énumérer les voisins de u devient alors une simple boucle sur cette liste, et c'est la boucle la plus fréquente de tout le chapitre — elle apparaîtra dans chacun des algorithmes qui suivent.

// La boucle « pour chaque » vue dans Les éléments de C++ : elle demande
// à `voisins[u]` ses éléments un par un, sans indice à tenir.
for (int v : voisins[u]) {
    cout << v << " ";
}

Son coût est proportionnel au degré sortant de u — pas à n. C'est toute la différence avec la matrice, et c'est de là que vient l'écart de complexité des parcours.

En revanche, cette forme perd ce que la matrice offrait : pour savoir si l'arc (u, v) existe, il faut chercher v dans la liste de u, donc la parcourir. Le test passe de Θ(1) à Θ(degré de u).

vector<vector<int>> voisins(6);

void ajouterArete(int u, int v) {
    voisins[u].push_back(v);
    voisins[v].push_back(u);
}

ajouterArete(0, 1);
ajouterArete(0, 3);
ajouterArete(1, 2);
ajouterArete(3, 4);

Dense ou creux : le choix qui décide

Le choix entre les deux formes n'est pas affaire de goût, et il se tranche par un calcul qui prend dix secondes. Voici d'abord ce que chacune coûte, opération par opération.

La dernière ligne est celle qui décide, parce qu'un parcours complet est ce que font presque tous les algorithmes du chapitre. Et pour la lire, il faut un vocabulaire de plus. Un graphe est dense quand m approche son plafond n², et creux quand m reste de l'ordre de n.

Pourquoi 30 000 et pas un million ? Parce qu'une intersection réelle a trois ou quatre routes, jamais dix mille — et c'est vrai de presque tous les graphes du monde réel. Un sommet a un nombre borné de voisins, si bien que m croît comme n et non comme n². Le web, les réseaux sociaux, les réseaux de transport, les dépendances entre tâches : tous creux.

D'où la règle pratique, et le fait qu'elle penche franchement d'un côté : les listes d'adjacence sont le choix par défaut, et la matrice ne se justifie que sur un graphe vraiment dense, ou quand le programme passe son temps à demander « cet arc précis existe-t-il ? » sans jamais énumérer de voisins. C'est aussi le choix du cours : l'énoncé du deuxième travail pratique impose d'implanter son réseau aérien « en utilisant un vecteur de listes d'adjacence ».

for (int u = 0; u < N; u++) {
    for (int v = 0; v < N; v++) {
        if (matrice[u][v]) traiter(u, v);
    }
}

L'onde qui se propage : le parcours en largeur

Le graphe est rangé ; il faut maintenant le traverser. « Traverser » veut dire une chose précise : visiter chaque sommet atteignable depuis un départ, une fois et une seule. Et cette dernière exigence est plus subtile qu'elle n'en a l'air — dans une liste chaînée, on ne peut pas repasser deux fois au même endroit, alors qu'un graphe avec un cycle y conduit tout seul.

D'où la pièce commune aux deux parcours, celle qu'il faut voir avant les algorithmes eux-mêmes : un tableau de booléens, un par sommet, qui note ce qu'on a déjà rencontré. Sans lui, un graphe cyclique fait tourner n'importe quel parcours indéfiniment.

Pour avancer par couches, il faut se souvenir des sommets rencontrés mais pas encore traités, et les reprendre dans l'ordre où on les a rencontrés. C'est exactement le contrat d'une file — premier entré, premier sorti — que le module Les structures linéaires a détaillée. Rien à réapprendre : on l'emploie telle quelle.

void parcoursLargeur(int depart, const vector<vector<int>>& voisins) {
    int n = voisins.size();

    // vector<bool> visite(n, false) — n booléens, tous initialisés à false.
    //   Le second argument du constructeur est la VALEUR de remplissage.
    vector<bool> visite(n, false);
    queue<int> file;                 // la file de la STL : push, front, pop

    visite[depart] = true;           // marqué AVANT d'entrer dans la file
    file.push(depart);

    while (!file.empty()) {
        int u = file.front();        // front() LIT, il ne retire pas
        file.pop();                  // pop() retire, il ne rend rien
        traiter(u);

        for (int v : voisins[u]) {
            if (!visite[v]) {
                visite[v] = true;    // marqué ici, pas au défilement
                file.push(v);
            }
        }
    }
}

const vector<vector<int>>& reprend la référence constante des Les éléments de C++ : on évite de recopier tout le graphe à chaque appel, sans s'autoriser à le modifier.

Lire ce code ligne à ligne ne suffit pas à savoir ce qu'il produit. Déroulons-le sur le graphe de référence, départ en A. La colonne qui compte est celle de la file : c'est elle qui décide de tout.

Ordre de traitement : A, B, D, C, E, F. Les couches se lisent directement dedans : A est à distance 0 ; B et D à distance 1 ; C, E et F à distance 2. Le parcours a bien fini la couche 1 avant d'entamer la couche 2.

Regarde le tour 3 et le tour 5 : le parcours ne fait rien. C'est là que le tableau visite travaille — sans lui, E serait entré une seconde fois dans la file au tour 3, F au tour 5, et chacun aurait été traité deux fois.

La plongée et le retour : le parcours en profondeur

L'autre parcours renverse la stratégie. Au lieu d'explorer tout ce qui est proche avant d'aller plus loin, il choisit une direction et s'y enfonce le plus loin possible, quitte à ne revenir qu'une fois bloqué.

Revenir au dernier embranchement, c'est reprendre les sommets dans l'ordre inverse de leur découverte. C'est le contrat d'une pile — dernier entré, premier sorti. Et il se trouve qu'on dispose déjà d'une pile sans avoir à l'écrire : la pile d'appels de la récursion en est une, et c'est ce qui rend la version récursive si courte.

// `visite` est passé par référence NON constante : chaque appel récursif
// doit écrire dans le MÊME tableau que son appelant. Une copie ferait
// repartir le marquage de zéro à chaque descente, et le parcours
// tournerait sans fin sur un graphe cyclique.
void parcoursProfondeur(int u, const vector<vector<int>>& voisins,
                        vector<bool>& visite) {
    visite[u] = true;
    traiter(u);

    for (int v : voisins[u]) {
        if (!visite[v]) {
            parcoursProfondeur(v, voisins, visite);   // on PLONGE ici
        }
    }
    // Rien après la boucle : arriver ici, c'est avoir épuisé tous les
    // voisins de u. La fonction rend la main, et l'appelant reprend son
    // propre `for` là où il l'avait laissé. C'est ça, le retour arrière.
}

L'appel initial demande le tableau de marquage : vector<bool> visite(n, false); parcoursProfondeur(depart, voisins, visite);

Ce code est plus court que celui du BFS et bien plus difficile à dérouler, parce que la structure qui gouverne tout — la pile — n'y apparaît nulle part. Voici donc la même trace, avec la pile d'appels rendue visible. Départ en A, toujours sur le graphe de référence.

Ordre de traitement : A, B, C, F, E, D. Compare-le à celui du BFS — A, B, D, C, E, F. Le même graphe, le même départ, deux ordres franchement différents : D est visité en deuxième position par l'un et en dernière par l'autre.

Regarde surtout la ligne où B « reprend son for ». C'est le geste que le code ne montre pas et que la trace rend visible : quand un appel rend la main, l'appelant ne recommence pas, il continue sa boucle à l'élément suivant. Tout le retour arrière du DFS tient dans ce mécanisme, et il est offert par la récursion.

On peut aussi écrire le DFS avec une pile explicite, ce qui est utile quand le graphe est profond au point de saturer la pile d'appels. Mais il faut savoir ce qu'on y perd.

void parcoursProfondeurIteratif(int depart, const vector<vector<int>>& voisins) {
    vector<bool> visite(voisins.size(), false);
    stack<int> pile;                 // la pile de la STL : push, top, pop
    pile.push(depart);

    while (!pile.empty()) {
        int u = pile.top();
        pile.pop();

        // On marque au DÉPILEMENT, pas à l'empilement : contrairement au
        // BFS, un même sommet peut avoir été empilé plusieurs fois avant
        // d'être atteint. Ce `continue` écarte les entrées en double.
        if (visite[u]) continue;
        visite[u] = true;
        traiter(u);

        for (int v : voisins[u]) {
            if (!visite[v]) pile.push(v);
        }
    }
}

Même graphe, même départ : cette version traite A, D, E, F, B, C. Ce n'est pas l'ordre de la version récursive.

void explorer(int u, const vector<vector<int>>& voisins,
              vector<bool>& visite) {
    visite[u] = true;
    for (int v : voisins[u]) {
        if (!visite[v]) explorer(v, voisins, visite);
    }
    cout << u << " ";           // <-- APRÈS la boucle, pas avant
}

Ce que chaque parcours trouve

Les deux parcours visitent exactement les mêmes sommets — tout ce qui est atteignable depuis le départ, ni plus ni moins. Ils ne diffèrent que par l'ordre, et ce qui suit dit ce que chacun achète avec le sien.

marquer(depart);
attente.ajouter(depart);

while (!attente.vide()) {
    u = attente.retirer();       // <-- LA SEULE LIGNE QUI DIFFÈRE
    traiter(u);

    for (int v : voisins[u]) {
        if (!marque(v)) {
            marquer(v);
            attente.ajouter(v);
        }
    }
}
// attente = file  -> parcours en LARGEUR
// attente = pile  -> parcours en PROFONDEUR

Reste à chiffrer ce que coûte un parcours, et la dérivation vaut d'être faite une fois plutôt que retenue. En listes d'adjacence, chaque sommet est mis dans l'attente au plus une fois — le marquage le garantit —, ce qui donne un travail proportionnel à n. Et pour chaque sommet traité, on parcourt sa liste de voisins : en sommant sur tous les sommets, on parcourt donc chaque arc exactement une fois, d'où un travail proportionnel à m. Total : Θ(n + m), c'est-à-dire Θ(V + E).

En matrice, la première moitié ne change pas, mais la seconde devient Θ(n) par sommet traité — il faut balayer une ligne entière pour trouver les voisins — soit Θ(n²) au total. C'est l'écart chiffré dans la section « Dense ou creux », et le voici expliqué : il ne vient pas du parcours, il vient de la façon dont on demande ses voisins à un sommet.

Ce que chacun permet de calculer se déduit de la troisième ligne, et c'est le programme du module suivant. Le BFS sert partout où la distance en nombre de liens compte : le plus court trajet dans un réseau non pondéré, tous les sommets à moins de k pas, le test de bipartition. Le DFS sert partout où l'ordre de sortie compte : détecter un cycle, trier des tâches par dépendance, identifier les groupes de sommets qui se rejoignent mutuellement.

Et il reste une question que ni l'un ni l'autre ne sait traiter : si les arcs portaient des poids, aucun de ces deux ordres ne donnerait le chemin le moins coûteux. C'est là que le module suivant commence.

stack<int> attente;              // c'était : queue<int> file
attente.push(depart);
visite[depart] = true;

while (!attente.empty()) {
    int u = attente.top();       // c'était : file.front()
    attente.pop();
    traiter(u);
    for (int v : voisins[u]) {
        if (!visite[v]) { visite[v] = true; attente.push(v); }
    }
}