Qu'est-ce qui est le mieux, les listes d'adjacence ou les matrices d'adjacence pour les problèmes de graphes en C++ ?

Question

Qu'est-ce qui est le mieux, les listes d'adjacence ou les matrices d'adjacence, pour les problèmes de graphes en C++ ? Quels sont les avantages et les inconvénients de chacune ?

Answer 1

Cela dépend du problème.

Matrice d'adjacence

• Utilise une mémoire de O(n^2)
• Il est rapide de rechercher et de vérifier la présence ou l'absence d'un bord spécifique.
  entre deux noeuds quelconques O(1)
• C'est lent d'itérer sur tous les bords
• Il est lent d'ajouter/supprimer un nœud ; une opération complexe O(n^2)
• Il est rapide d'ajouter un nouveau bord O(1)

Liste d'adjacence

• L'utilisation de la mémoire dépend davantage du nombre d'arêtes (et moins du nombre de nœuds),
  ce qui peut économiser beaucoup de mémoire si la matrice d'adjacence est peu dense.
• Trouver la présence ou l'absence d'un bord spécifique entre deux nœuds quelconques.
  est légèrement plus lent qu'avec la matrice O(k), où k est le nombre de nœuds voisins.
• Il est rapide d'itérer sur toutes les arêtes car vous pouvez accéder directement aux voisins de n'importe quel nœud.
• Il est rapide d'ajouter/supprimer un nœud, plus facile que la représentation matricielle.
• Il est rapide d'ajouter un nouveau bord O(1)

Answer 2

Cette réponse ne concerne pas uniquement le C++ puisque tout ce qui est mentionné concerne les structures de données elles-mêmes, indépendamment du langage. Et ma réponse suppose que vous connaissez la structure de base des listes et des matrices d'adjacence.

Mémoire

Si la mémoire est votre principale préoccupation, vous pouvez suivre cette formule pour un graphique simple qui autorise les boucles :

Une matrice d'adjacence occupe n 2 /Espace de 8 octets (un bit par entrée).

Une liste d'adjacence occupe 8e espace, où e est le nombre d'arêtes (ordinateur 32 bits).

Si nous définissons la densité du graphique comme d = e/n 2 (nombre d'arêtes divisé par le nombre maximal d'arêtes), nous pouvons trouver le "point de rupture" où une liste occupe plus de mémoire qu'une matrice :

8e > n 2 /8 quand d > 1/64

Ainsi, avec ces chiffres (toujours spécifiques aux 32 bits), le point d'arrêt se situe à l'endroit suivant 1/64 . Si la densité (e/n 2 ) est supérieure à 1/64, alors a matrice est préférable si vous voulez économiser de la mémoire.

Vous pouvez lire à ce sujet sur le site wikipedia (article sur les matrices d'adjacence) et beaucoup d'autres sites.

Note complémentaire : On peut améliorer l'efficacité spatiale de la matrice d'adjacence en utilisant une table de hachage où les clés sont des paires de sommets (non dirigés uniquement).

Itération et recherche

Les listes d'adjacence sont un moyen compact de représenter uniquement les arêtes existantes. Cependant, cela se fait au prix d'une recherche éventuellement lente d'arêtes spécifiques. Puisque chaque liste est aussi longue que le degré d'un sommet, le temps de recherche le plus défavorable pour vérifier une arête spécifique peut devenir O(n), si la liste n'est pas ordonnée. Cependant, la recherche des voisins d'un sommet devient triviale, et pour un graphe peu dense ou petit, le coût de l'itération à travers les listes d'adjacence peut être négligeable.

Les matrices d'adjacence, quant à elles, utilisent plus d'espace afin de fournir un temps de consultation constant. Puisque chaque entrée possible existe, vous pouvez vérifier l'existence d'un bord en temps constant en utilisant des index. Cependant, la recherche de voisins prend O(n) puisqu'il faut vérifier tous les voisins possibles. L'inconvénient évident en termes d'espace est que pour les graphes épars, beaucoup de remplissage est ajouté. Voir la discussion sur la mémoire ci-dessus pour plus d'informations à ce sujet.

Si vous n'êtes toujours pas sûr de ce que vous devez utiliser : La plupart des problèmes du monde réel produisent des graphes épars et/ou de grande taille, qui sont mieux adaptés aux représentations de listes d'adjacence. Elles peuvent sembler plus difficiles à mettre en œuvre mais je vous assure qu'elles ne le sont pas, et lorsque vous écrivez un BFS ou un DFS et que vous voulez récupérer tous les voisins d'un nœud, elles ne sont qu'à une ligne de code. Cependant, notez que je ne fais pas la promotion des listes d'adjacence en général.

Answer 3

Cela dépend de ce que vous recherchez.

Avec matrices d'adjacence vous pouvez répondre rapidement à des questions visant à déterminer si une arête spécifique entre deux sommets appartient au graphe, et vous pouvez également procéder à des insertions et des suppressions rapides d'arêtes. Le site inconvénient est que vous devez utiliser un espace excessif, en particulier pour les graphes avec beaucoup de sommets, ce qui est très inefficace surtout si votre graphe est clairsemé.

D'autre part, avec listes d'adjacence il est plus difficile de vérifier si une arête donnée se trouve dans un graphe, car il faut chercher dans la liste appropriée pour trouver l'arête, mais ils sont plus économes en espace.

En général, cependant, les listes d'adjacence sont la structure de données appropriée pour la plupart des applications des graphes.

Answer 4

Si vous envisagez d'analyser des graphiques en C++, le premier endroit où commencer est probablement le module bibliothèque de graphes boost qui met en œuvre un certain nombre d'algorithmes, dont BFS.

• Docs sur la bibliothèque graphique Boost

EDIT

Cette question précédente sur SO vous aidera probablement :

comment-créer-un-graphe-undirigé-et-le-traverser-en-profondeur-du-premier-searc h

Answer 5

Pour compléter la réponse de keyser5053 sur l'utilisation de la mémoire.

Pour tout graphe dirigé, une matrice d'adjacence (à 1 bit par arête) consomme n^2 * (1) bits de mémoire.

Pour un graphique complet une liste d'adjacence (avec des pointeurs de 64 bits) consomme n * (n * 64) bits de mémoire, sans tenir compte de la surcharge de la liste.

Pour un graphe incomplet, une liste d'adjacence consomme 0 bits de mémoire, sans tenir compte de la surcharge de la liste.

---

Pour une liste d'adjacence, vous pouvez utiliser la formule suivante pour déterminer le nombre maximum d'arêtes ( e ) avant qu'une matrice d'adjacence soit optimale pour la mémoire.

edges = n^2 / s pour déterminer le nombre maximum d'arêtes, où s est la taille du pointeur de la plate-forme.

Si votre graphe est mis à jour de façon dynamique, vous pouvez maintenir cette efficacité avec un nombre moyen d'arêtes (par nœud) de n / s .

---

Quelques exemples avec des pointeurs 64 bits et un graphe dynamique (Un graphe dynamique met à jour la solution d'un problème de manière efficace après des changements, plutôt que de la recalculer à partir de zéro à chaque fois qu'un changement a été effectué).

Pour un graphe dirigé, où n est 300, le nombre optimal d'arêtes par nœud en utilisant une liste d'adjacence est :

= 300 / 64
= 4

Si on met ça dans la formule de Keyser5053, d = e / n^2 (où e est le nombre total d'arêtes), nous pouvons voir que nous sommes en dessous du point de rupture ( 1 / s ) :

d = (4 * 300) / (300 * 300)
d < 1/64
aka 0.0133 < 0.0156

Cependant, 64 bits pour un pointeur peut être excessif. Si, à la place, vous utilisez des entiers de 16 bits comme décalages de pointeur, nous pouvons faire tenir jusqu'à 18 bords avant le point de rupture.

= 300 / 16
= 18

d = ((18 * 300) / (300^2))
d < 1/16
aka 0.06 < 0.0625

Chacun de ces exemples ignore la surcharge des listes d'adjacence elles-mêmes ( 64*2 pour un vecteur et des pointeurs de 64 bits).