Structures de données pour stocker des graphes : aperçu des solutions existantes et deux « presque nouvelles »

Bonjour à tous.

Dans cette note, j'ai décidé de lister les principales structures de données utilisées pour stocker des graphes en informatique, ainsi que de parler de quelques autres structures qui ont comme par magie « cristallisé » à mes yeux.

Alors, commençons. Mais pas par le début – je pense que nous savons tous ce qu'est un graphe et quels types il existe (orientés, non orientés, pondérés, non pondérés, avec des arêtes multiples et des boucles ou sans).

Alors, allons-y. Quelles sont donc les options de structures de données pour le « stockage de graphes » que nous avons.

1. Structures de données matricielles

1.1 Matrice d'adjacence. La matrice d'adjacence est une matrice où les en-têtes des lignes et des colonnes correspondent aux numéros des sommets du graphe, et la valeur de chaque élément a(i,j) est déterminée par la présence ou l'absence d'arêtes entre les sommets i et j (il est évident que pour un graphe non orienté, cette matrice sera symétrique, ou nous pouvons convenir que toutes les valeurs sont stockées uniquement au-dessus de la diagonale principale). Pour les graphes non pondérés, a(i,j) peut être défini par le nombre d'arêtes de i à j (si aucune arête n'existe, alors a(i,j)= 0), et pour les graphes pondérés, également par le poids (le poids total) des arêtes mentionnées.

1.2 Matrice d'incidence. Dans ce cas, notre graphe est également stocké dans un tableau, où généralement les numéros des lignes correspondent aux numéros de ses sommets, et les numéros des colonnes aux arêtes numérotées au préalable. Si un sommet et une arête sont incident aux autres, une valeur non nulle est enregistrée dans la cellule correspondante (pour les graphes non orientés, 1 est enregistré en cas d'incidence d'un sommet et d'une arête ; pour les graphes orientés, c'est « 1 » si l'arête « sort » du sommet et « -1 » si elle « entre » dans celui-ci (c'est assez facile à retenir, car le signe « moins » entre également dans le nombre « -1 »)). Pour les graphes pondérés, encore une fois, au lieu de 1 et -1, on peut indiquer le poids total de l'arête.

2. Structures de données énumératives

2.1 Liste d'adjacence. Ici, tout semble assez simple. À chaque sommet d'un graphe, en général, on peut associer n'importe quelle structure énumérative (liste, vecteur, tableau, …) dans laquelle seront stockés les numéros de tous les sommets adjacents. Pour les graphes orientés, nous n'inclurons dans cette liste que les sommets vers lesquels il existe une arête « dirigée » à partir du sommet de référence. Pour les graphes pondérés, la mise en œuvre sera plus complexe.

2.2 Liste des arêtes. Une structure de données assez populaire. La liste des arêtes, comme le suggère le Capitaine Évidence, représente en effet la liste proprement dite des arêtes du graphe, chacune étant définie par un sommet de départ, un sommet d'arrivée (pour les graphes non orientés, l'ordre n'a pas d'importance, bien qu'il soit possible d'utiliser différentes règles, par exemple, indiquer les sommets dans l'ordre croissant) et un poids (uniquement pour les graphes pondérés).

Pour les listes-matrices mentionnées ci-dessus, vous pouvez consulter plus en détail (avec des illustrations) par exemple ici.

2.3 Tableau d'adjacence. Ce n'est pas une structure très courante. Essentiellement, il représente une forme « d'emballage » des listes d'adjacence dans une seule structure énumérative (tableau, vecteur). Les premiers n (selon le nombre de sommets du graphe) éléments de ce tableau contiennent les index de départ du même tableau, à partir desquels sont consécutivement enregistrés tous les sommets adjacents.

Voici l'explication la plus claire (pour moi) que j'ai trouvée : ejuo.livejournal.com/4518.html

3. Vecteur d'adjacence et tableau associatif d'adjacence

Il se trouve que l'auteur de ces lignes, n'étant pas un programmeur professionnel, mais ayant parfois eu affaire à des graphes, a le plus souvent manipulé des listes d'arêtes. En effet, c'est pratique lorsque le graphe compte des boucles multiples et des arêtes. Et donc, pour faire évoluer les listes d'arêtes classiques, je vous propose de prêter attention à leur « développement/ramification/variation » en particulier : le vecteur d'adjacence et le tableau associatif d'adjacence.

3.1 Vecteur d'adjacence

Cas (a1) : graphe non pondéré

Nous allons appeler le vecteur d'adjacence pour un graphe non pondéré un ensemble ordonné d'un nombre pair d'entiers (a[2i], a[2i+1],…, où i commence à 0), où chaque paire de nombres a[2i], a[2i+1] définit une arête du graphe entre les sommets a[2i] et a[2i+1].
Ce format d'enregistrement ne contient pas d'informations sur la direction du graphe (les deux options sont possibles). Lors de l'utilisation du format pour un graphe orienté, il est supposé que l'arête est dirigée de a[2i] vers a[2i+1]. Ici et plus loin : pour les graphes non orientés, si nécessaire, des exigences peuvent être appliquées concernant l'ordre d'enregistrement des sommets (par exemple, pour que le sommet avec la valeur assignée la plus basse soit en premier).

En C++, il est judicieux de représenter le vecteur d'adjacence à l'aide de std::vector, c'est pourquoi ce nom a été choisi pour cette structure de données.

Cas (a2) : graphe non pondéré, poids des arêtes entières

Par analogie avec le cas (a1), nous appellerons vecteur d'adjacence pour un graphe pondéré avec des poids d'arêtes entiers un ensemble ordonné (tableau dynamique) de nombres (a[3i], a[3i+1], a[3i+2],…, où i commence à 0), où chaque « triplet » de nombres a[3i], a[3i+1], a[3i+2] définit une arête du graphe entre les sommets numérotés a[3i] et a[3i+1] respectivement, et la valeur a[3i+2] est le poids de cette arête. Ce graphe peut être orienté ou non.

Cas (b) : graphe non pondéré, poids des arêtes non entiers

Étant donné qu'il n'est pas possible de stocker des éléments hétérogènes dans un même tableau (vecteur), une implémentation possible serait la suivante. Le graphe est stocké dans une paire de vecteurs, où le premier vecteur est le vecteur d'adjacence du graphe sans indication des poids, et le second vecteur contient les poids correspondants (implémentation possible pour C++ : std::pair). Ainsi, pour une arête définie par une paire de sommets aux indices 2i, 2i+1 du premier vecteur, le poids sera égal à l'élément à l'indice i du second vecteur.

Mais pourquoi est-ce nécessaire ?

Eh bien, pour l'auteur de ces lignes, pour résoudre un certain nombre de problèmes, cela semble assez utile. Et d'un point de vue formel, cela présente les avantages suivants :

• Le vecteur d'adjacence, comme toute autre structure « énumérative », est assez compact, occupe moins de mémoire qu'une matrice d'adjacence (pour des graphes épars), et est relativement simple à mettre en œuvre.
• Les sommets d'un graphe peuvent en principe être marqués par des nombres négatifs. Au cas où ce genre de « déviation » serait nécessaire.
• Les graphes peuvent contenir des arêtes multiples et des boucles multiples, chacune ayant des poids différents (positifs, négatifs, voire nuls). Il n'y a pas de restrictions à cet égard.
• De plus, il est possible d'attribuer différentes propriétés aux arêtes – mais à ce sujet, voir point 4.

Cependant, il faut reconnaître que cet "array de liste" ne prévoit pas d'accès rapide à l'arête. Et c'est ici qu'intervient le tableau associatif d'adjacence, comme expliqué ci-dessous.

3.2 Tableau associatif d'adjacence

Donc, si l'accès à une arête spécifique, à son poids et à d'autres propriétés est critique pour nous, et que les exigences en matière de mémoire n'autorisent pas l'utilisation d'une matrice d'adjacence, réfléchissons à comment nous pourrions modifier le vecteur d'adjacence pour résoudre ce problème. Ainsi, la clé est l'arête du graphe, qui peut être représentée sous la forme d'une paire ordonnée d'entiers. À quoi cela ressemble-t-il? Ne serait-ce pas une clé dans le tableau associatif? Alors, pourquoi ne pas le réaliser? Imaginons que nous ayons un tableau associatif où chaque clé – une paire ordonnée d'entiers – est associée à une valeur – un entier ou un nombre réel définissant le poids de l'arête. En C++, il serait judicieux de réaliser cette structure sur la base du conteneur std::map (std::map <std::pair , int> ou std::map <std::pair , double>), ou de std::multimap en cas de plusieurs arêtes. Voilà, nous avons obtenu une structure pour stocker des graphes, qui occupe moins de mémoire que les structures "matricielles", qui peut représenter des graphes avec des boucles et des arêtes multiples et qui n'a même pas de exigences strictes sur la non-négativité des numéros de sommet (je ne sais pas à qui cela pourrait être utile, mais bon).

4. Structures de données, qu'elles soient "saturées", manquent de quelque chose

Et en effet: lors de la résolution de certains problèmes, il peut être nécessaire d'attribuer certaines caractéristiques aux arêtes du graphe et, par conséquent, de les stocker. Si ces caractéristiques peuvent être clairement réduites à des entiers, il est possible de stocker ces "graphes avec caractéristiques supplémentaires" en utilisant des versions étendues du vecteur d'adjacence et du tableau associatif d'adjacence.

Considérons donc un graphe non pondéré, pour chaque arête duquel il est nécessaire de stocker, par exemple, 2 propriétés supplémentaires définies par des entiers. Dans ce cas, il est possible de définir son vecteur d'adjacence comme un ensemble ordonné de « quartets » d'entiers (a[2i], a[2i+1], a[2i+2], a[2i+3]…), où a[2i+2] et a[2i+3] détermineront les propriétés de l'arête correspondante. Pour un graphe avec des poids d'arêtes entiers, l'ordre, en général, est similaire (la seule différence étant que les propriétés suivront le poids de l'arête et seront définies par les éléments a[2i+3] et a[2i+4], et l'arête elle-même sera définie par 5 nombres ordonnés au lieu de 4). Et pour un graphe avec des poids d'arêtes non entiers, les propriétés pourront être notées dans son composant non pondéré.

Lors de l'utilisation d'un tableau associatif d'adjacence pour des graphes avec des poids d'arêtes entiers, il est possible de définir, comme valeur, non pas un nombre individuel, mais un tableau (vecteur) de nombres, qui définit, en plus du poids de l'arête, toutes les autres propriétés nécessaires. Cependant, un inconvénient pour le cas des poids non entiers sera la nécessité de définir une propriété par un nombre à virgule flottante (oui, c'est un inconvénient, mais si ces propriétés ne sont pas trop nombreuses et si elles ne sont pas définies par des doubles trop « complexes », cela peut aller). Ainsi, en C++, les tableaux associatifs d'adjacence avancés peuvent être définis de la manière suivante : std::map <std::pair , std::vector> ou std::map <std::pair , std::vector>, où la première valeur dans le « vecteur-valeur-par-clé » sera le poids de l'arête, et ensuite se trouveront les désignations numériques de ses propriétés.

Littérature :

Sur les graphes et les algorithmes en général :

1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algorithmes : construction et analyse, 2ème édition : Trad. de l'anglais – Moscou : Éditions Williams, 2011.
2. Harari, Frank. Théorie des graphes. Moscou : Mir, 1973.
Rapport de l'auteur sur ce vecteur et le tableau associatif d'adjacence :
3. Tchernoukhov S.A. Vecteur d'adjacence et tableau d'adjacence comme façons de représenter et de stocker des graphes / S.A. Chernouhov. Vecteur d'adjacence et carte d'adjacence en tant que structures de données pour représenter un graphe // Recueil d'articles de la conférence scientifique et pratique internationale « Problèmes de mise en œuvre des résultats des développements innovants et voies de leur résolution » (Saratov, 14.09.2019). – Sterlitamak : AMI, 2019, p. 65-69
Sources Internet utiles sur le sujet :
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

Source : habr.com