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

129

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?

magiix
la source
21
La structure que vous utilisez ne dépend pas de la langue mais du problème que vous essayez de résoudre.
avakar
1
Je voulais un usage général comme l'algorithme djikstra, j'ai posé cette question car je ne sais pas si l'implémentation de la liste liée vaut la peine d'être essayée car il est plus difficile à coder que la matrice de contiguïté.
magiix
Les listes en C ++ sont aussi faciles que de taper std::list(ou mieux encore, std::vector).
avakar
1
@avakar: ou std::dequeou std::set. Cela dépend de la manière dont le graphique évoluera avec le temps et des algorithmes que vous comptez utiliser.
Alexandre C.

Réponses:

125

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)
Mark Byers
la source
les listes chaînées sont plus difficiles à coder, pensez-vous que la mise en œuvre vaut la peine de passer du temps à l'apprendre?
magiix
11
@magiix: Oui, je pense que vous devriez comprendre comment coder des listes chaînées si nécessaire, mais il est également important de ne pas réinventer la roue: cplusplus.com/reference/stl/list
Mark Byers
Quelqu'un peut-il fournir un lien avec un code propre pour, par exemple, une première recherche en largeur dans le format de listes liées?
magiix
Utilisation de std :: list geeksforgeeks.org/breadth-first-traversal-for-a-graph
atif93
78

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 2 (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 2 ) 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.

keyer
la source
9
+1 pour un aperçu, mais cela doit être corrigé par la structure de données réelle utilisée pour stocker les listes de contiguïté. Vous voudrez peut-être stocker pour chaque sommet sa liste de contiguïté sous forme de carte ou de vecteur, auquel cas les nombres réels dans vos formules doivent être mis à jour. En outre, des calculs similaires peuvent être utilisés pour évaluer les points de rentabilité pour la complexité temporelle d'algorithmes particuliers.
Alexandre C.
3
Ouais, cette formule est pour un scénario spécifique. Si vous voulez une réponse approximative, allez-y et utilisez cette formule, ou modifiez-la selon vos spécifications si nécessaire (par exemple, la plupart des gens ont un ordinateur 64 bits de nos jours :))
keyer
1
Pour les personnes intéressées, la formule du point de rupture (nombre maximum d'arêtes moyennes dans un graphique de n nœuds) est e = n / s, où sest la taille du pointeur.
deceleratedcaviar
33

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.

entrez la description de l'image ici

John Red
la source
Dans le cas où l'on ne sait pas si le graphe est dense ou clairsemé, serait-il juste de dire que la complexité spatiale pour une liste de contiguïté serait O (v + e)?
Pour la plupart des algorithmes pratiques, l'une des opérations les plus importantes consiste à itérer sur toutes les arêtes sortant d'un sommet donné. Vous voudrez peut-être l'ajouter à votre liste - c'est O (degré) pour AL et O (V) pour AM.
max
@johnred n'est-il pas préférable de dire que l'ajout d'un sommet (temps) pour AL est O (1) parce qu'au lieu de O (en) parce que nous n'ajoutons pas vraiment d'arêtes lors de l'ajout d'un sommet. L'ajout d'un bord peut être traité comme une opération distincte. Pour AM, il est logique de tenir compte, mais même là, nous devons simplement initialiser les lignes et la colonne pertinentes du nouveau sommet à zéro. L'ajout d'arêtes même pour AM peut être pris en compte séparément.
Usman
Comment ajouter un sommet à AL O (V)? Nous devons créer une nouvelle matrice, y copier les valeurs précédentes. Ce devrait être O (v ^ 2).
Alex_ban
19

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.

Alex Ntousias
la source
Et si vous utilisez des dictionnaires pour stocker la liste de contiguïté, cela vous donnera la présence d'un bord en temps amorti O (1).
Rohith Yeravothula
10

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

Exemple de graphique
entrez la description de l'image ici

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 2 . 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 2 ). (Vous pouvez simplement utiliser la partie triangulaire supérieure de la matrice pour déterminer toutes les arêtes mais ce sera à nouveau Θ (n 2 ))

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

entrez la description de l'image ici
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

Muhammed Kadir
la source
7

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.

É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

Nerd binaire
la source
Merci, je vais vérifier cette bibliothèque
magiix
+1 pour le graphique de boost. C'est la voie à suivre (sauf bien sûr si c'est à des fins éducatives)
Tristram Gräbener
5

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.)

Evgeni Sergeev
la source
2
Pour les algorithmes tels que DFS et BFS, si vous utilisez une matrice, vous devez vérifier la ligne entière chaque fois que vous souhaitez trouver des nœuds adjacents, alors que vous avez déjà des nœuds adjacents dans une liste adjacente. Pourquoi pensez-vous an adjacency list is as good as a matrixdans ces cas?
realUser404
@ realUser404 Exactement, le balayage d'une ligne entière de matrice est une opération O (n). Les listes de contiguïté sont meilleures pour les graphes épars lorsque vous devez traverser toutes les arêtes sortantes, elles peuvent le faire en O (d) (d: degré du nœud). Les matrices ont de meilleures performances de cache que les listes de contiguïté cependant, en raison de l'accès séquentiel, donc pour des graphiques un peu denses, l'analyse d'une matrice peut avoir plus de sens.
Jochem Kuijpers
3

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).

décéléré
la source
Je ne comprends pas le rôle d = (4 * 300) / (300 * 300), ne devrait-il pas être d = 4 / (300 * 300)? Puisque la formule est d = e / n^2.
Saurabh le
2

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?

ChrisOdney
la source
1

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).

max
la source
1

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.

justcoding121
la source
Pour la matrice de contiguïté, supprimer le sommet prend O (V ^ 2) et non O (V)
Saurabh
Oui. Mais si vous utilisez un dictionnaire pour suivre les indices du tableau, il descendra à O (V). Jetez un œil à cette implémentation de RemoveVertex .
justcoding121