Trois façons de stocker un graphique en mémoire, avantages et inconvénients

Question

Il existe trois façons de stocker un graphique en mémoire :

1. Nœuds en tant qu'objets et arêtes en tant que pointeurs
2. Une matrice contenant tous les poids des bords entre le nœud numéroté x et le nœud y.
3. Une liste d'arêtes entre des nœuds numérotés

Je sais comment écrire les trois, mais je ne suis pas sûr d'avoir pensé à tous les avantages et inconvénients de chacun.

Quels sont les avantages et les inconvénients de chacune de ces façons de stocker un graphique en mémoire ?

Answer 1

L'une des façons de les analyser est en termes de complexité de la mémoire et du temps (qui dépend de la façon dont vous voulez accéder au graphique).

Stockage des nœuds en tant qu'objets avec des pointeurs les uns vers les autres

• La complexité de la mémoire pour cette approche est O(n) car il y a autant d'objets que de nœuds. Le nombre de pointeurs (vers les nœuds) requis est de O(n^2) car chaque objet nœud peut contenir des pointeurs pour un maximum de nœuds.
• La complexité temporelle de cette structure de données est O(n) pour l'accès à un nœud donné.

Stockage d'une matrice de poids d'arêtes

• Cela représenterait une complexité mémoire de O(n^2) pour la matrice.
• L'avantage de cette structure de données est que la complexité temporelle pour accéder à un nœud donné est O(1).

En fonction de l'algorithme que vous exécutez sur le graphe et du nombre de nœuds, vous devrez choisir une représentation appropriée.

Answer 2

Quelques éléments supplémentaires à prendre en compte :

1. Le modèle matriciel se prête plus facilement aux graphes avec des bords pondérés, en stockant les poids dans la matrice. Le modèle objet/pointeur devrait stocker les poids des arêtes dans un tableau parallèle, ce qui nécessite une synchronisation avec le tableau de pointeurs.

2. Le modèle objet/pointeur fonctionne mieux avec les graphes dirigés qu'avec les graphes non dirigés car les pointeurs devraient être maintenus par paires, ce qui peut devenir non synchronisé.

Answer 3

La méthode des objets et des pointeurs souffre de la difficulté de la recherche, comme certains l'ont noté, mais elle est assez naturelle pour faire des choses comme construire des arbres de recherche binaires, où il y a beaucoup de structure supplémentaire.

Personnellement, j'adore les matrices d'adjacence car elles facilitent grandement toutes sortes de problèmes, en utilisant des outils issus de la théorie algébrique des graphes. (La puissance k de la matrice d'adjacence donne le nombre de chemins de longueur k du sommet i au sommet j, par exemple. Ajoutez une matrice d'identité avant de prendre la puissance k pour obtenir le nombre de chemins de longueur <=k. Prendre une mineure de rang n-1 du Laplacien pour obtenir le nombre d'arbres spanning... Et ainsi de suite).

Mais tout le monde dit que les matrices d'adjacence sont coûteuses en mémoire ! Ils n'ont qu'à moitié raison : Vous pouvez contourner ce problème en utilisant des matrices éparses lorsque votre graphe a peu d'arêtes. Les structures de données de matrices éparses font exactement le même travail que la simple conservation d'une liste d'adjacence, mais disposent de toute la gamme des opérations matricielles standard, ce qui vous donne le meilleur des deux mondes.

Answer 4

Je pense que votre premier exemple est un peu ambigu : les nœuds sont des objets et les bords des pointeurs. Vous pourriez garder la trace de ces derniers en stockant uniquement un pointeur vers un nœud racine, auquel cas l'accès à un nœud donné peut être inefficace (disons que vous voulez le nœud 4 - si l'objet nœud n'est pas fourni, vous devrez peut-être le chercher). Dans ce cas, vous perdriez également des portions du graphe qui ne sont pas accessibles à partir du nœud racine. Je pense que c'est le cas que f64 rainbow suppose quand il dit que la complexité temporelle pour accéder à un noeud donné est O(n).

Sinon, vous pourriez également conserver un tableau (ou hashmap) rempli de pointeurs vers chaque nœud. Cela permet un accès O(1) à un nœud donné, mais augmente un peu l'utilisation de la mémoire. Si n est le nombre de nœuds et e le nombre d'arêtes, la complexité spatiale de cette approche serait de O(n + e).

La complexité spatiale de l'approche matricielle serait de l'ordre de O(n^2) (en supposant que les bords sont unidirectionnels). Si votre graphe est clairsemé, vous aurez beaucoup de cellules vides dans votre matrice. Mais si votre graphe est entièrement connecté (e = n^2), cela se compare favorablement avec la première approche. Comme le dit RG, vous pouvez également avoir moins de ratés de cache avec cette approche si vous allouez la matrice comme un seul morceau de mémoire, ce qui pourrait rendre le suivi de beaucoup d'arêtes autour du graphe plus rapide.

La troisième approche est probablement la plus efficace en termes d'espace pour la plupart des cas - O(e) - mais elle rendrait la recherche de tous les bords d'un nœud donné une tâche O(e). Je ne peux pas penser à un cas où cela serait très utile.

Answer 5

D'accord, donc si les arêtes n'ont pas de poids, la matrice peut être un tableau binaire, et l'utilisation d'opérateurs binaires peut faire avancer les choses très, très vite dans ce cas.

Si le graphe est clairsemé, la méthode objet/pointeur semble beaucoup plus efficace. Maintenir les objets/pointeurs dans une structure de données afin de les rassembler en un seul morceau de mémoire pourrait également être un bon plan, ou toute autre méthode pour les faire rester ensemble.

La liste d'adjacence - simplement une liste de nœuds connectés - semble de loin la plus efficace en termes de mémoire, mais probablement aussi la plus lente.

Inverser un graphe dirigé, c'est facile avec la représentation matricielle, et facile avec la liste d'adjacence, mais pas si bien avec la représentation objet/pointeur.