Quoi de mieux, les listes de contiguïté ou les matrices de contiguïté pour les problèmes de graphes en C ++?

Quoi de mieux, les listes de contiguïté ou la matrice de contiguïté, pour les problèmes de graphes en C ++? Quels sont les avantages et les inconvénients de chacun?

Cela dépend du problème.

Matrice d'adjacence

• Utilise la mémoire 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 nœuds quelconques O (1)
• Il est lent à parcourir tous les bords
• L'ajout / la suppression d'un nœud est lent; une opération complexe O (n ^ 2)
• Il est rapide d'ajouter une nouvelle arête O (1)

Liste de proximité

• L'utilisation de la mémoire dépend du nombre d'arêtes (et non du nombre de nœuds),
  ce qui peut économiser beaucoup de mémoire si la matrice de contiguïté est clairsemée
• Trouver la présence ou l'absence d'une arête 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 tous les bords car vous pouvez accéder directement à n'importe quel nœud voisin
• 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)

Cette réponse ne concerne pas uniquement le C ++ puisque tout ce qui est mentionné concerne les structures de données elles-mêmes, quel que soit le langage. Et ma réponse suppose que vous connaissez la structure de base des listes et des matrices de contiguïté.

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 ^deux / 8 Surface d'octets (un bit par entrée).

Une liste de contiguïté occupe 8e espace, où e est le nombre d'arêtes (ordinateur 32 bits).

Si nous définissons la densité du graphe comme d = e / n ² (nombre d'arêtes divisé par le nombre maximum d'arêtes), nous pouvons trouver le "point d'arrêt" où une liste prend plus de mémoire qu'une matrice:

8e> n ^deux / 8 quand d> 1/64

Donc, avec ces nombres (toujours spécifiques à 32 bits), le point d'arrêt arrive à 1/64 . Si la densité (e / n ² ) est supérieure à 1/64, une matrice est préférable si vous souhaitez économiser de la mémoire.

Vous pouvez lire à ce sujet sur wikipedia (article sur les matrices de contiguïté) et sur de nombreux autres sites.

Note d'accompagnement : on peut améliorer l'efficacité spatiale de la matrice de contiguïté en utilisant une table de hachage où les clés sont des paires de sommets (non dirigées uniquement).

Itération et recherche

Les listes de contiguïté 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. Etant donné que 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, rechercher les voisins d'un sommet devient trivial, et pour un graphe clairsemé ou petit, le coût de l'itération à travers les listes de contiguïté peut être négligeable.

Les matrices d'adjacence, quant à elles, utilisent plus d'espace afin de fournir un temps de recherche constant. Puisque toutes les entrées possibles existent, vous pouvez vérifier l'existence d'une arête en temps constant à l'aide d'index. Cependant, la recherche de voisins prend O (n) car vous devez vérifier tous les voisins possibles. L'inconvénient évident de l'espace est que pour les graphes clairsemés, beaucoup de remplissage est ajouté. Voir la discussion sur la mémoire ci-dessus pour plus d'informations à ce sujet.

Si vous ne savez toujours pas quoi utiliser : la plupart des problèmes du monde réel produisent des graphiques clairsemés et / ou volumineux, qui conviennent mieux aux représentations de listes de contiguïté. Ils peuvent sembler plus difficiles à implémenter, mais je vous assure qu'ils 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, ils ne sont qu'à une ligne de code. Cependant, notez que je ne fais pas la promotion des listes de contiguïté en général.

D'accord, j'ai compilé les complexités temporelles et spatiales des opérations de base sur les graphiques.
L'image ci-dessous doit être explicite.
Notez comment la matrice d'adjacence est préférable lorsque nous nous attendons à ce que le graphique soit dense, et comment la liste d'adjacence est préférable lorsque nous nous attendons à ce que le graphique soit clairsemé.
J'ai fait quelques hypothèses. Demandez-moi si une complexité (temps ou espace) nécessite des éclaircissements. (Par exemple, pour un graphique clairsemé, j'ai pris En pour une petite constante, car j'ai supposé que l'ajout d'un nouveau sommet n'ajoutera que quelques arêtes, car nous nous attendons à ce que le graphique reste clairsemé même après l'ajout de cela sommet.)

Veuillez me dire s'il y a des erreurs.

Cela dépend de ce que vous recherchez.

Avec les matrices de contiguïté, vous pouvez répondre rapidement aux questions concernant si une arête spécifique entre deux sommets appartient au graphe, et vous pouvez également avoir des insertions et des suppressions rapides d'arêtes. L' inconvénient est que vous devez utiliser un espace excessif, en particulier pour les graphiques avec de nombreux sommets, ce qui est très inefficace surtout si votre graphique est clairsemé.

D'un autre côté, avec les listes de contiguïté, il est plus difficile de vérifier si une arête donnée est dans un graphique, car vous devez rechercher dans la liste appropriée pour trouver l'arête, mais elles sont plus efficaces en termes d'espace.

Cependant, en général, les listes de contiguïté constituent la bonne structure de données pour la plupart des applications de graphiques.

Supposons que nous ayons un graphe qui a n nombre de nœuds et m nombre d'arêtes,

Exemple de graphique

Matrice d'adjacence: Nous créons une matrice qui a n nombre de lignes et de colonnes donc en mémoire, elle prendra un espace proportionnel à n ² . Vérifier si deux nœuds nommés u et v ont une arête entre eux prendra Θ (1) temps. Par exemple, la vérification de (1, 2) est qu'un bord ressemblera à ce qui suit dans le code:

if(matrix[1][2] == 1)

Si vous voulez identifier tous les bords, vous devez itérer sur la matrice, cela nécessitera deux boucles imbriquées et cela prendra Θ (n ² ). (Vous pouvez simplement utiliser la partie triangulaire supérieure de la matrice pour déterminer toutes les arêtes mais ce sera à nouveau Θ (n ² ))

Liste d'adjacence: Nous créons une liste que chaque nœud pointe également vers une autre liste. Votre liste aura n éléments et chaque élément pointera vers une liste dont le nombre d'éléments est égal au nombre de voisins de ce nœud (regardez l'image pour une meilleure visualisation). Il faudra donc de l'espace mémoire proportionnel à n + m . Vérifier si (u, v) est une arête prendra un temps O (deg (u)) dans lequel deg (u) est égal au nombre de voisins de u. Parce qu'au plus, vous devez parcourir la liste pointée par le u. L'identification de toutes les arêtes prendra Θ (n + m).

Liste de contiguïté d'un exemple de graphique

Vous devez faire votre choix en fonction de vos besoins. A cause de ma réputation je n'ai pas pu mettre d'image de matrice, désolé pour ça

Si vous envisagez l'analyse de graphes en C ++, le premier point de départ serait probablement la bibliothèque de graphes boost , qui implémente un certain nombre d'algorithmes, y compris BFS.

• Boost Graph Library Docs

ÉDITER

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

comment à créer-ac-boost-undirected-graph-et-traverse-il en profondeur d'abord searc- h

Il vaut mieux y répondre avec des exemples.

Pensez à Floyd-Warshall par exemple. Nous devons utiliser une matrice de contiguïté, sinon l'algorithme sera asymptotiquement plus lent.

Ou que faire s'il s'agit d'un graphe dense sur 30 000 sommets? Ensuite, une matrice de contiguïté pourrait avoir du sens, car vous stockerez 1 bit par paire de sommets, plutôt que les 16 bits par arête (le minimum dont vous auriez besoin pour une liste de contiguïté): c'est 107 Mo, plutôt que 1,7 Go.

Mais pour des algorithmes comme DFS, BFS (et ceux qui l'utilisent, comme Edmonds-Karp), la recherche prioritaire (Dijkstra, Prim, A *), etc., une liste de contiguïté est aussi bonne qu'une matrice. Eh bien, une matrice peut avoir un léger bord lorsque le graphique est dense, mais uniquement par un facteur constant banal. (Combien? C'est une question d'expérimentation.)

Pour ajouter à la réponse de keyser5053 sur l'utilisation de la mémoire.

Pour tout graphe orienté, une matrice de contiguïté (à 1 bit par front) consomme des n^2 * (1)bits de mémoire.

Pour un graphique complet , une liste de contiguïté (avec des pointeurs de 64 bits) consomme des n * (n * 64)bits de mémoire, à l'exclusion de la surcharge de la liste.

Pour un graphique incomplet, une liste de contiguïté consomme des 0bits de mémoire, à l'exclusion de la surcharge de la liste.

Pour une liste de contiguïté, vous pouvez utiliser la formule suivante pour déterminer le nombre maximal d'arêtes ( e) avant qu'une matrice de contiguïté ne soit optimale pour la mémoire.

edges = n^2 / spour déterminer le nombre maximal d'arêtes, où sest la taille du pointeur de la plate-forme.

Si votre graphique est mis à jour dynamiquement, vous pouvez maintenir cette efficacité avec un nombre moyen de bords (par nœud) de n / s.

Quelques exemples avec des pointeurs 64 bits et un graphe dynamique (Un graphe dynamique met à jour efficacement la solution d'un problème après les modifications, plutôt que de la recalculer à partir de zéro à chaque fois qu'une modification a été apportée.)

Pour un graphe orienté, où nest 300, le nombre optimal d'arêtes par nœud utilisant une liste de contiguïté est:

= 300 / 64
= 4

Si nous le connectons à la formule de keyser5053, d = e / n^2(où eest le nombre total de bords), 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 peuvent être exagérés. Si vous utilisez à la place des entiers 16 bits comme décalages de pointeur, nous pouvons ajuster jusqu'à 18 arêtes 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 de contiguïté elles-mêmes ( 64*2pour un vecteur et des pointeurs 64 bits).

En fonction de l'implémentation de la matrice d'adjacence, le «n» du graphe doit être connu plus tôt pour une implémentation efficace. Si le graphique est trop dynamique et nécessite une expansion de la matrice de temps en temps, cela peut également être considéré comme un inconvénient?

Si vous utilisez une table de hachage au lieu de la matrice ou de la liste de contiguïté, vous obtiendrez un meilleur temps d'exécution et un espace Big-O pour toutes les opérations (vérifier un bord est O(1), obtenir tous les bords adjacents O(degree), etc.).

Il y a cependant une surcharge de facteur constante pour le temps d'exécution et l'espace (la table de hachage n'est pas aussi rapide que la liste liée ou la recherche de tableau, et prend une quantité décente d'espace supplémentaire pour réduire les collisions).

Je vais simplement aborder la question de surmonter le compromis de la représentation régulière de la liste de contiguïté, puisque d'autres réponses ont couvert d'autres aspects.

Il est possible de représenter un graphique dans une liste de contiguïté avec une requête EdgeExists en temps constant amorti, en tirant parti des structures de données Dictionary et HashSet . L'idée est de garder les sommets dans un dictionnaire, et pour chaque sommet, nous gardons un ensemble de hachage faisant référence à d'autres sommets avec lesquels il a des arêtes.

Un compromis mineur dans cette implémentation est qu'elle aura une complexité spatiale O (V + 2E) au lieu de O (V + E) comme dans une liste de contiguïté régulière, puisque les arêtes sont représentées deux fois ici (car chaque sommet a son propre ensemble de hachage des bords). Mais des opérations telles que AddVertex , AddEdge , RemoveEdge peuvent être effectuées en temps amorti O (1) avec cette implémentation, sauf pour RemoveVertex qui prend O (V) comme matrice de contiguïté. Cela signifierait qu'à part la simplicité de mise en œuvre, la matrice de contiguïté n'a aucun avantage spécifique. Nous pouvons économiser de l'espace sur un graphe clairsemé avec presque les mêmes performances dans cette implémentation de liste de contiguïté.

Jetez un œil aux implémentations ci-dessous dans le référentiel Github C # pour plus de détails. Notez que pour le graphique pondéré, il utilise un dictionnaire imbriqué au lieu d'une combinaison dictionnaire-ensemble de hachage afin de prendre en charge la valeur de poids. De même pour le graphe orienté, il existe des ensembles de hachage séparés pour les arêtes d'entrée et de sortie.

Algorithmes avancés

Remarque: je crois qu'en utilisant la suppression paresseuse, nous pouvons optimiser davantage l' opération RemoveVertex à O (1) amorti, même si je n'ai pas testé cette idée. Par exemple, lors de la suppression, marquez simplement le sommet comme supprimé dans le dictionnaire, puis effacez paresseusement les bords orphelins pendant d'autres opérations.