Qu'est-ce qui est mieux, des listes de contiguïté ou des matrices de contiguïté pour les problèmes de graphiques en C++?

Cela dépend du problème.

Une matrice de contiguïté utilise O(n*n) de la mémoire. Il a des recherches rapides pour vérifier la présence ou l'absence d'un bord spécifique, mais lent à itérer sur tous les bords.

utilisent la mémoire en proportion des bords de nombre, ce qui pourrait sauver beaucoup de mémoire si la matrice de contiguïté est clairsemée. Il est rapide pour itérer sur tous les bords, mais trouver la présence ou l'absence bord spécifique est légèrement plus lent qu'avec le matrice.

cette réponse n'est pas seulement pour 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 est de supposer que vous connaissez la structure de base des listes et 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 permet des boucles:

Une matrice de contiguïté occupe n ² /8 octets d'espace (un bits par entrée).

une liste de contiguïté occupe 8e espace, où e est le nombre de bords (32 bits ordinateur).

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 de rupture" où une liste prend plus de mémoire qu'une matrice:

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

donc avec ces nombres (encore spécifiques à 32 bits) le point de rupture atterrit à 1/64 . Si la densité (e/n ² ) est supérieure à 1/64, alors un matrice est préférable si vous voulez sauver la mémoire.

vous pouvez lire à ce sujet à wikipedia (article sur les matrices de contiguïté) et beaucoup d'autres sites.

Side note : on peut améliorer l'efficacité spatiale de la matrice d'adjacence en utilisant une table de hachage où les touches sont des paires de Sommets (Non dirigées seulement).

itération et recherche

sont un moyen compact de représenter uniquement les bords existants. Toutefois, cela se fait au prix d'une recherche peut-être lente des arêtes spécifiques. Comme chaque liste est aussi long que le degré d'un sommet le pire temps de recherche de cas de vérifier un bord spécifique peut devient O (n), si la liste n'est pas classée. Cependant, la recherche des voisins d'un vertex devient triviale, et pour un graphe clairsemé ou petit, le coût de l'itération à travers les listes de contiguïté pourrait être négligeable.

utilisent plus d'espace pour fournir un temps de recherche 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 voisinage prend O (n) puisque vous devez vérifier tous les voisins possibles. L'espace inconvénient est que pour les graphes éparses beaucoup de rembourrage est ajouté. Voir la discussion sur la mémoire ci-dessus pour plus d'information à ce sujet.

si vous n'êtes pas encore sûr de ce qu'il faut utiliser : la plupart des problèmes du monde réel produisent des graphiques épars et/ou grands, qui sont mieux adaptés pour les représentations de liste de contiguïté. Ils peuvent sembler plus difficiles à mettre en œuvre, mais je vous assure qu'ils ne le sont pas, et quand vous écrivez un BFS ou DFS et que vous voulez aller chercher tout les voisins d'un nœud 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.

OK, j'ai compilé les complexités spatiales et temporelles des opérations de base sur des graphiques.

L'image ci-dessous doivent être auto-explicatif.

Remarquez comment la matrice de contiguïté est préférable quand nous nous attendons à ce que le graphe soit dense, et comment la liste de contiguïté est préférable quand nous nous attendons à ce que le graphe soit clairsemé.

J'ai fait quelques hypothèses. Demandez-moi si une complexité (temps ou espace) doit être clarifiée. (Par exemple, pour un graphique clairsemé, J'ai pris En pour une petite constante, car j'ai supposé que l'ajout d'un nouveau vertex n'ajoutera que quelques arêtes, parce que nous nous attendons à ce que le graphe reste clairsemé même après avoir ajouté ce vertex.)

dites-moi s'il y a des erreurs.

ça dépend de ce que vous cherchez.

avec matrices d'adjacence vous pouvez répondre rapidement aux questions concernant si un bord spécifique entre deux sommets appartient au graphe, et vous pouvez également avoir des insertions rapides et des suppressions de bords. Le 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ée.

d'autre part, avec " listes de contiguïté il est plus difficile de vérifier si un bord donné est dans un graphe, parce que vous devez chercher à travers la liste appropriée pour trouver le bord, mais ils sont plus efficace de l'espace.

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

si vous regardez analyse de graphe en C++ probablement le premier endroit pour commencer serait le bibliothèque de graphe boost , qui met en œuvre un certain nombre d'algorithmes y compris BFS.

• Boost Graph Library Docs

MODIFIER

Cette question ne sera DONC probablement de l'aide:

how-to-create-a-c-boost-pure-graphique-et-traverse-il-en-depth-first-search h

il est préférable de répondre par des exemples.

Penser de Floyd-Warshall par exemple. Nous devons utiliser une matrice de contiguïté, ou l'algorithme va être asymptotiquement plus lent.

ou s'il s'agit d'un graphe dense sur 30 000 sommets? Alors 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 bord (le minimum dont vous auriez besoin pour une liste de contiguïté): c'est 107 MB, plutôt que de 1,7 GO.

mais pour les algorithmes comme DFS, BFS (et ceux qui l'utilisent, comme Edmonds-Karp), priorité-première recherche (Dijkstra, Prim, a*), etc., une liste de contiguïté est aussi bonne qu'une matrice. Eh bien, une matrice pourrait avoir un léger bord quand le graphe est dense, mais seulement par un facteur constant Non remarquable. (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 dirigé, une matrice de contiguïté (à 1 bit par bord) consomme n^2 * (1) bits de mémoire.

pour un graphe complet , une liste de contiguïté (avec 64 pointeurs de bits) consomme n * (n * 64) bits de mémoire, à l'exclusion de la liste au-dessus.

pour un graphique incomplet, une liste de contiguïté consomme 0 bits of memory, à l'exclusion de la liste des frais généraux.

pour une liste de contiguïté, vous pouvez utiliser la formule suivante pour déterminer le nombre maximum de bords ( e ) avant qu'une matrice de contiguïté soit optimale pour la mémoire.

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

si vous êtes graphique est une mise à jour dynamique, vous pouvez maintenir cette efficacité avec un nombre moyen d'arêtes (par noeud) de n / s .

quelques exemples (avec des pointeurs 64 bits).

pour un graphe dirigé, où n est 300, le nombre optimal d'arêtes par noeud en utilisant une liste de contiguïté est:

= 300 / 64
= 4

si on le branche dans la formule de keyser5053, d = e / n^2 (où e est le nombre total d'arêtes), on voit que nous sommes au-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 exagéré. Si vous utilisez plutôt des entiers de 16bit comme déport 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 le au-dessus des listes de contiguïté elles-mêmes ( 64*2 pour un vecteur et des pointeurs 64 bits).

selon la mise en œuvre de la matrice de contiguïté, le " n " du graphique doit être connu plus tôt pour une mise en œuvre efficace. Si le graphique est trop dynamique et nécessite une extension de la matrice, chaque maintenant et puis, qui peut aussi être considéré comme un inconvénient?

si vous utilisez une table de hachage à la place d'une matrice ou d'une liste de contiguïté, vous obtiendrez un meilleur ou le même Big-O run-time et de l'espace pour toutes les opérations (vérification d'un bord est O(1) , obtenir tous les bords adjacents est O(degree) , etc.).

il y a un facteur constant au-dessus mais pour le temps d'exécution et l'espace (la table de hachage n'est pas aussi rapide que la liste liée ou le tableau de recherche, et prend un espace supplémentaire de quantité décente pour réduire les collisions).

laisse supposer que nous avons un graphique qui a n nombre de noeuds et m nombre d'arêtes,

exemple de graphique

Matrice De Contiguïté: Nous créons une matrice qui a n nombre de lignes et de colonnes afin d'en mémoire de l'espace proportionnel à n ² . Vérifier si deux noeuds nommés u et v ont un bord entre eux prendra Θ(1) Temps. Par exemple, vérifier si (1, 2) est 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 demandera deux boucles imbriquées et il faudra Θ(n ² ). (Vous pouvez simplement utiliser le haut partie triangulaire de la matrice pour déterminer tous les bords mais il sera de nouveau Θ(N ² ))

Liste D'Adjacence: Nous sommes en train de créer une liste que chaque noeud pointe également vers une autre liste. Votre liste aura n éléments et chaque élément pointera vers une liste qui a le nombre d'articles qui est égal au nombre de voisins de ce noeud (regarder l'image pour une meilleure visualisation). Donc il va prendre de l'espace dans la mémoire, est proportionnel à n+m . Vérifier si (u, v) est un bord prend le temps O(deg(u)) dans lequel deg(u) égale le nombre de voisins de U. Parce que tout au plus, vous devez itérer sur la liste qui est pointée par le u. L'identification de toutes les arêtes prendra Θ (n+m).

liste de contiguïté exemple de graphique

Vous devez faire votre choix en fonction de vos besoins. à cause de ma réputation Je ne pouvais pas mettre l'image de matrix, désolé pour ce

je vais juste parler 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 graphe dans la liste de contiguïté avec EdgeExists requête en temps constant amorti en profitant de Dictionary et HashSet structures de données. L'idée est de garder les sommets dans un dictionnaire et pour chaque sommet, nous garder un hachage ensemble de référencement vers d'autres sommets, il a des bords.

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

regardez les implémentations ci-dessous dans le dépôt GitHub C# pour plus de détails. Notez que pour le graphe pondéré il utilise un dictionnaire imbriqué au lieu de dictionnaire de hachage combinaison de façon à tenir compte de la valeur de poids. De même pour le graphique dirigé il y a des ensembles séparés de hachage pour les bords d'entrée et de sortie.

Avancé Des Algorithmes De

Note: je crois que l'utilisation de suppression paresseuse nous pouvons optimiser davantage RemoveVertex opération à O (1) amorti même si je n'ai pas testé cette idée. Par exemple lors de la suppression il suffit de marquer le sommet comme supprimé dans le dictionnaire, puis bords orphelins clairs paresseusement au cours d'autres opérations.