Was ist besser, Adjazenzlisten oder Adjazenzmatrizen für Diagrammprobleme in C ++?

129

Was ist besser, Adjazenzlisten oder Adjazenzmatrix für Grafikprobleme in C ++? Was sind die Vor- und Nachteile von jedem?

magiix
quelle
21
Die von Ihnen verwendete Struktur hängt nicht von der Sprache ab, sondern von dem Problem, das Sie lösen möchten.
Avakar
1
Ich meinte für den allgemeinen Gebrauch wie den Djikstra-Algorithmus, ich stellte diese Frage, weil ich nicht weiß, dass die Implementierung einer verknüpften Liste einen Versuch wert ist, weil es schwieriger zu codieren ist als die Adjazenzmatrix.
Magiix
Listen in C ++ sind so einfach wie das Eingeben std::list(oder noch besser std::vector).
Avakar
1
@avakar: oder std::dequeoder std::set. Dies hängt davon ab, wie sich das Diagramm mit der Zeit ändert und welche Algorithmen Sie darauf ausführen möchten.
Alexandre C.

Antworten:

125

Das hängt vom Problem ab.

Adjazenzmatrix

  • Verwendet O (n ^ 2) Speicher
  • Es ist schnell zu suchen und zu prüfen, ob eine bestimmte Kante
    zwischen zwei beliebigen Knoten vorhanden ist oder nicht. O (1)
  • Es ist langsam, über alle Kanten zu iterieren
  • Das Hinzufügen / Löschen eines Knotens ist langsam. eine komplexe Operation O (n ^ 2)
  • Es ist schnell, eine neue Kante O (1) hinzuzufügen.

Adjazenzliste

  • Die Speichernutzung hängt von der Anzahl der Kanten ab (nicht von der Anzahl der Knoten).
    Dies kann viel Speicherplatz sparen, wenn die Adjazenzmatrix dünn ist
  • Das Finden des Vorhandenseins oder Nichtvorhandenseins einer spezifischen Kante zwischen zwei beliebigen Knoten
    ist etwas langsamer als bei der Matrix O (k); Dabei ist k die Anzahl der Nachbarknoten
  • Es ist schnell, über alle Kanten zu iterieren, da Sie direkt auf alle Knotennachbarn zugreifen können
  • Es ist schnell, einen Knoten hinzuzufügen / zu löschen. einfacher als die Matrixdarstellung
  • Es ist schnell, eine neue Kante O (1) hinzuzufügen.
Mark Byers
quelle
Verknüpfte Listen sind schwieriger zu codieren. Glauben Sie, dass die Implementierung es wert ist, einige Zeit damit zu verbringen, sie zu lernen?
Magiix
11
@magiix: Ja, ich denke, Sie sollten verstehen, wie man verknüpfte Listen bei Bedarf codiert
Mark Byers
Kann jemand einen Link mit einem sauberen Code für die erste Breitensuche im Format für verknüpfte Listen bereitstellen?
Magiix
78

Diese Antwort gilt nicht nur für C ++, da sich alles, was erwähnt wird, auf die Datenstrukturen selbst bezieht, unabhängig von der Sprache. Meine Antwort geht davon aus, dass Sie die Grundstruktur von Adjazenzlisten und -matrizen kennen.

Erinnerung

Wenn der Speicher Ihr Hauptanliegen ist, können Sie diese Formel für ein einfaches Diagramm befolgen, das Schleifen zulässt:

Eine Adjazenzmatrix nimmt n 2 /8 - Byte - Raum (ein Bit pro Eintrag).

Eine Adjazenzliste belegt 8e Platz, wobei e die Anzahl der Kanten ist (32-Bit-Computer).

Wenn wir die Dichte des Graphen als d = e / n 2 definieren (Anzahl der Kanten geteilt durch die maximale Anzahl der Kanten), können wir den "Haltepunkt" finden, an dem eine Liste mehr Speicherplatz beansprucht als eine Matrix:

8e> n 2 /8 , wenn d> 1/64

Mit diesen Zahlen (immer noch 32-Bit-spezifisch) landet der Haltepunkt also bei 1/64 . Wenn die Dichte (e / n 2 ) größer als 1/64 ist, ist eine Matrix vorzuziehen, wenn Sie Speicher sparen möchten.

Sie können darüber auf Wikipedia (Artikel über Adjazenzmatrizen) und vielen anderen Websites lesen .

Randnotiz : Sie können die Raumeffizienz der Adjazenzmatrix verbessern, indem Sie eine Hash-Tabelle verwenden, bei der die Schlüssel Paare von Eckpunkten sind (nur ungerichtet).

Iteration und Nachschlagen

Adjazenzlisten sind eine kompakte Methode, um nur vorhandene Kanten darzustellen. Dies geht jedoch zu Lasten einer möglicherweise langsamen Suche nach bestimmten Kanten. Da jede Liste so lang ist wie der Grad eines Scheitelpunkts, kann die Suchzeit im ungünstigsten Fall für die Überprüfung einer bestimmten Kante O (n) werden, wenn die Liste ungeordnet ist. Das Nachschlagen der Nachbarn eines Scheitelpunkts wird jedoch trivial, und für ein spärliches oder kleines Diagramm können die Kosten für das Durchlaufen der Adjazenzlisten vernachlässigbar sein.

Adjazenzmatrizen hingegen benötigen mehr Platz, um eine konstante Suchzeit zu gewährleisten. Da jeder mögliche Eintrag vorhanden ist, können Sie mithilfe von Indizes in konstanter Zeit prüfen, ob eine Kante vorhanden ist. Die Nachbarsuche benötigt jedoch O (n), da Sie alle möglichen Nachbarn überprüfen müssen. Der offensichtliche Platznachteil besteht darin, dass bei spärlichen Diagrammen viel Polsterung hinzugefügt wird. Weitere Informationen hierzu finden Sie in der obigen Speicherdiskussion.

Wenn Sie sich immer noch nicht sicher sind, was Sie verwenden sollen : Die meisten Probleme in der realen Welt erzeugen spärliche und / oder große Diagramme, die sich besser für die Darstellung von Adjazenzlisten eignen. Sie scheinen schwieriger zu implementieren zu sein, aber ich versichere Ihnen, dass dies nicht der Fall ist. Wenn Sie ein BFS oder DFS schreiben und alle Nachbarn eines Knotens abrufen möchten, sind sie nur eine Codezeile entfernt. Beachten Sie jedoch, dass ich Adjazenzlisten im Allgemeinen nicht bewerbe.

Keyser
quelle
9
+1 für Einsicht, aber dies muss durch die tatsächliche Datenstruktur korrigiert werden, die zum Speichern der Adjazenzlisten verwendet wird. Möglicherweise möchten Sie für jeden Scheitelpunkt seine Adjazenzliste als Karte oder Vektor speichern. In diesem Fall müssen die tatsächlichen Zahlen in Ihren Formeln aktualisiert werden. Ähnliche Berechnungen können auch verwendet werden, um Break-Even-Punkte für die zeitliche Komplexität bestimmter Algorithmen zu bewerten.
Alexandre C.
3
Ja, diese Formel ist für ein bestimmtes Szenario. Wenn Sie eine grobe Antwort wünschen, verwenden Sie diese Formel oder ändern Sie sie nach Bedarf gemäß Ihren Spezifikationen (zum Beispiel haben die meisten Leute heutzutage einen 64-Bit-Computer :))
Keyser
1
Für Interessenten lautet die Formel für die Bruchstelle (maximale Anzahl der durchschnittlichen Kanten in einem Diagramm mit n Knoten) e = n / s, wobei sdie Zeigergröße ist.
Verlangsamte
33

Okay, ich habe die zeitliche und räumliche Komplexität grundlegender Operationen in Diagrammen zusammengestellt.
Das Bild unten sollte selbsterklärend sein.
Beachten Sie, wie die Adjazenzmatrix vorzuziehen ist, wenn wir erwarten, dass das Diagramm dicht ist, und wie die Adjazenzliste vorzuziehen ist, wenn wir erwarten, dass das Diagramm dünn ist.
Ich habe einige Annahmen gemacht. Fragen Sie mich, ob eine Komplexität (Zeit oder Raum) geklärt werden muss. (Beispiel: Für ein Diagramm mit geringer Dichte habe ich En als kleine Konstante angenommen, da ich davon ausgegangen bin, dass durch Hinzufügen eines neuen Scheitelpunkts nur wenige Kanten hinzugefügt werden, da wir davon ausgehen, dass das Diagramm auch nach dem Hinzufügen dünn bleibt Scheitel.)

Bitte sagen Sie mir, wenn es Fehler gibt.

Geben Sie hier die Bildbeschreibung ein

John Red
quelle
Falls nicht bekannt ist, ob der Graph dicht oder dünn ist, wäre es richtig zu sagen, dass die Raumkomplexität für eine Adjazenzliste O (v + e) ​​wäre?
Für die meisten praktischen Algorithmen besteht eine der wichtigsten Operationen darin, alle Kanten zu durchlaufen, die aus einem bestimmten Scheitelpunkt herausgehen. Vielleicht möchten Sie es Ihrer Liste hinzufügen - es ist O (Grad) für AL und O (V) für AM.
Max
@johnred ist es nicht besser zu sagen, dass das Hinzufügen eines Scheitelpunkts (Zeit) für AL O (1) ist, weil anstelle von O (en) keine Kanten beim Hinzufügen eines Scheitelpunkts hinzugefügt werden. Das Hinzufügen einer Kante kann als separate Operation behandelt werden. Für AM ist es sinnvoll zu berücksichtigen, aber selbst dort müssen wir nur relevante Zeilen und Spalten des neuen Scheitelpunkts auf Null initialisieren. Das Hinzufügen von Kanten auch für AM kann separat berücksichtigt werden.
Usman
Wie fügt man AL O (V) einen Scheitelpunkt hinzu? Wir müssen eine neue Matrix erstellen und die vorherigen Werte in diese kopieren. Es sollte O (v ^ 2) sein.
Alex_ban
19

Es kommt darauf an, wonach Sie suchen.

Mit Adjazenzmatrizen können Sie schnell Fragen beantworten, ob eine bestimmte Kante zwischen zwei Scheitelpunkten zum Diagramm gehört, und Sie können Kanten schnell einfügen und löschen. Der Nachteil ist, dass Sie übermäßig viel Platz benötigen, insbesondere für Diagramme mit vielen Scheitelpunkten, was besonders dann ineffizient ist, wenn Ihr Diagramm spärlich ist.

Andererseits ist es bei Adjazenzlisten schwieriger zu überprüfen, ob sich eine bestimmte Kante in einem Diagramm befindet, da Sie die entsprechende Liste durchsuchen müssen, um die Kante zu finden, diese jedoch platzsparender sind.

Im Allgemeinen sind Adjazenzlisten jedoch die richtige Datenstruktur für die meisten Anwendungen von Diagrammen.

Alex Ntousias
quelle
Was passiert, wenn Sie Wörterbücher zum Speichern der Adjazenzliste verwenden, um eine Kante in der amortisierten O (1) -Zeit zu erhalten?
Rohith Yeravothula
10

Nehmen wir an, wir haben einen Graphen mit n Knoten und m Kanten.

Beispieldiagramm
Geben Sie hier die Bildbeschreibung ein

Adjazenzmatrix: Wir erstellen eine Matrix mit n Zeilen und Spalten, sodass im Speicher Platz benötigt wird, der proportional zu n 2 ist . Die Überprüfung, ob zwischen zwei Knoten mit den Namen u und v eine Kante liegt, dauert Θ (1). Wenn Sie beispielsweise nach (1, 2) suchen, sieht eine Kante im Code wie folgt aus:

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

Wenn Sie alle Kanten identifizieren möchten, müssen Sie über die Matrix iterieren. Dies erfordert zwei verschachtelte Schleifen und es wird Θ (n 2 ) benötigt. (Sie können einfach den oberen dreieckigen Teil der Matrix verwenden, um alle Kanten zu bestimmen, aber es wird wieder Θ (n 2 ) sein.)

Adjazenzliste: Wir erstellen eine Liste, die jeder Knoten auch auf eine andere Liste verweist. Ihre Liste enthält n Elemente und jedes Element zeigt auf eine Liste mit einer Anzahl von Elementen, die der Anzahl der Nachbarn dieses Knotens entspricht (siehe Bild zur besseren Visualisierung). Es wird also Speicherplatz im Speicher benötigt, der proportional zu n + m ist . Die Überprüfung, ob (u, v) eine Kante ist, dauert O (Grad (u)) Zeit, in der Grad (u) der Anzahl der Nachbarn von u entspricht. Denn höchstens müssen Sie über die Liste iterieren, auf die das u zeigt. Das Identifizieren aller Kanten dauert Θ (n + m).

Adjazenzliste des Beispieldiagramms

Geben Sie hier die Bildbeschreibung ein
Sie sollten Ihre Wahl nach Ihren Bedürfnissen treffen. Aufgrund meines Rufs konnte ich kein Bild von der Matrix erstellen, tut mir leid

Muhammed Kadir
quelle
7

Wenn Sie sich die Diagrammanalyse in C ++ ansehen, ist der erste Startpunkt wahrscheinlich die Boost-Diagrammbibliothek , die eine Reihe von Algorithmen einschließlich BFS implementiert.

BEARBEITEN

Diese vorherige Frage zu SO wird wahrscheinlich helfen:

Wie erstelle ich einen AC-Boost-ungerichteten Graphen und durchquere ihn in der Tiefe? Erstes Suchen h

Binärer Nerd
quelle
Vielen Dank, ich werde diese Bibliothek überprüfen
Magiix
+1 für Boost-Graph. Dies ist der richtige Weg (außer natürlich, wenn es zu Bildungszwecken ist)
Tristram Gräbener
5

Dies lässt sich am besten mit Beispielen beantworten.

Denken Sie zum Beispiel an Floyd-Warshall . Wir müssen eine Adjazenzmatrix verwenden, sonst ist der Algorithmus asymptotisch langsamer.

Oder was ist, wenn es sich um ein dichtes Diagramm auf 30.000 Eckpunkten handelt? Dann könnte eine Adjazenzmatrix sinnvoll sein, da Sie 1 Bit pro Scheitelpunktpaar speichern und nicht die 16 Bits pro Kante (das Minimum, das Sie für eine Adjazenzliste benötigen würden): Das sind 107 MB statt 1,7 GB.

Für Algorithmen wie DFS, BFS (und diejenigen, die es verwenden, wie Edmonds-Karp), Priority-First-Suche (Dijkstra, Prim, A *) usw. ist eine Adjazenzliste so gut wie eine Matrix. Nun, eine Matrix könnte eine leichte Kante haben, wenn der Graph dicht ist, aber nur durch einen unauffälligen konstanten Faktor. (Wie viel? Es geht ums Experimentieren.)

Evgeni Sergeev
quelle
2
Wenn Sie bei Algorithmen wie DFS und BFS eine Matrix verwenden, müssen Sie jedes Mal die gesamte Zeile überprüfen, wenn Sie benachbarte Knoten suchen möchten, während Sie bereits benachbarte Knoten in einer benachbarten Liste haben. Warum denkst du an adjacency list is as good as a matrixin diesen Fällen?
RealUser404
@ realUser404 Genau das Scannen einer ganzen Matrixzeile ist eine O (n) -Operation. Adjazenzlisten eignen sich besser für Diagramme mit geringer Dichte, wenn Sie alle ausgehenden Kanten durchlaufen müssen. Sie können dies in O (d) (d: Grad des Knotens) tun. Matrizen haben aufgrund des sequentiellen Zugriffs eine bessere Cache-Leistung als Adjazenzlisten. Bei etwas dichteren Diagrammen kann das Scannen von Matrizen sinnvoller sein.
Jochem Kuijpers
3

Hinzufügen zur Antwort von keyser5053 zur Speichernutzung.

Für jeden gerichteten Graphen verbraucht eine Adjazenzmatrix (mit 1 Bit pro Kante) n^2 * (1)Speicherbits.

Für ein vollständiges Diagramm verbraucht eine Adjazenzliste (mit 64-Bit-Zeigern) n * (n * 64)Speicherbits, ausgenommen Listen-Overhead.

Bei einem unvollständigen Diagramm verbraucht eine Adjazenzliste 0Speicherbits, ausgenommen Listen-Overhead.


Für eine Adjazenzliste können Sie die folgende Formel verwenden, um die maximale Anzahl von Kanten ( e) zu bestimmen, bevor eine Adjazenzmatrix für den Speicher optimal ist.

edges = n^2 / sum die maximale Anzahl von Kanten zu bestimmen, wobei sdie Zeigergröße der Plattform ist.

Wenn Ihr Diagramm dynamisch aktualisiert wird, können Sie diese Effizienz mit einer durchschnittlichen Kantenanzahl (pro Knoten) von beibehalten n / s.


Einige Beispiele mit 64-Bit-Zeigern und dynamischem Diagramm (Ein dynamisches Diagramm aktualisiert die Lösung eines Problems nach Änderungen effizient, anstatt es jedes Mal nach einer Änderung von Grund auf neu zu berechnen.)

Für einen gerichteten Graphen mit n300 ist die optimale Anzahl von Kanten pro Knoten unter Verwendung einer Adjazenzliste:

= 300 / 64
= 4

Wenn wir dies in die Formel von keyser5053 einfügen d = e / n^2(wo eist die Gesamtzahl der Kanten), können wir sehen, dass wir uns unter dem Haltepunkt befinden ( 1 / s):

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

64 Bit für einen Zeiger können jedoch übertrieben sein. Wenn Sie stattdessen 16-Bit-Ganzzahlen als Zeigerversätze verwenden, können Sie bis zu 18 Kanten anpassen, bevor Sie den Bruchpunkt erreichen.

= 300 / 16
= 18

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

Jedes dieser Beispiele ignoriert den Overhead der Adjazenzlisten selbst ( 64*2für einen Vektor und 64-Bit-Zeiger).

verzögert kaviar
quelle
Ich verstehe den Teil nicht d = (4 * 300) / (300 * 300), sollte es nicht sein d = 4 / (300 * 300)? Da ist die Formel d = e / n^2.
Saurabh
2

Abhängig von der Adjacency Matrix-Implementierung sollte das 'n' des Diagramms für eine effiziente Implementierung früher bekannt sein. Wenn der Graph zu dynamisch ist und ab und zu eine Erweiterung der Matrix erfordert, kann dies auch als Nachteil gewertet werden?

ChrisOdney
quelle
1

Wenn Sie eine Hash-Tabelle anstelle einer Adjazenzmatrix oder -liste verwenden, erhalten Sie für alle Operationen eine bessere oder gleiche Big-O-Laufzeit und denselben Platz (Überprüfen auf eine Kante O(1), Abrufen aller benachbarten Kanten O(degree)usw.).

Es gibt jedoch einen konstanten Faktor-Overhead sowohl für die Laufzeit als auch für den Speicherplatz (die Hash-Tabelle ist nicht so schnell wie die Suche nach verknüpften Listen oder Arrays und benötigt eine angemessene Menge zusätzlichen Speicherplatz, um Kollisionen zu reduzieren).

max
quelle
1

Ich werde nur auf die Überwindung des Kompromisses bei der regelmäßigen Darstellung von Adjazenzlisten eingehen, da andere Antworten andere Aspekte abgedeckt haben.

Es ist möglich, ein Diagramm in einer Adjazenzliste mit der EdgeExists- Abfrage in einer amortisierten konstanten Zeit darzustellen , indem Dictionary- und HashSet- Datenstrukturen genutzt werden. Die Idee ist, Scheitelpunkte in einem Wörterbuch zu behalten, und für jeden Scheitelpunkt behalten wir einen Hash-Satz bei, der auf andere Scheitelpunkte verweist, mit denen er Kanten hat.

Ein kleiner Kompromiss bei dieser Implementierung besteht darin, dass die Raumkomplexität O (V + 2E) anstelle von O (V + E) wie in der regulären Adjazenzliste vorliegt, da Kanten hier zweimal dargestellt werden (da jeder Scheitelpunkt seine eigene Hash-Menge hat von Kanten). Operationen wie AddVertex , AddEdge , RemoveEdge können mit dieser Implementierung jedoch in der amortisierten Zeit O (1) ausgeführt werden, mit Ausnahme von RemoveVertex, das O (V) wie eine Adjazenzmatrix verwendet. Dies würde bedeuten, dass die Adjazenzmatrix außer der Einfachheit der Implementierung keinen spezifischen Vorteil hat. In dieser Implementierung der Adjazenzliste können wir Platz für spärliche Diagramme mit nahezu derselben Leistung sparen.

Weitere Informationen finden Sie in den folgenden Implementierungen im Github C # -Repository. Beachten Sie, dass für gewichtete Diagramme ein verschachteltes Wörterbuch anstelle einer Kombination aus Wörterbuch und Hash-Satz verwendet wird, um den Gewichtungswert zu berücksichtigen. In ähnlicher Weise gibt es für gerichtete Graphen separate Hash-Sets für In- und Out-Kanten.

Fortgeschrittene Algorithmen

Hinweis: Ich glaube, dass wir durch verzögertes Löschen die RemoveVertex- Operation weiter optimieren können , um O (1) amortisiert zu erhalten, obwohl ich diese Idee nicht getestet habe. Markieren Sie beispielsweise beim Löschen einfach den Scheitelpunkt als im Wörterbuch gelöscht und löschen Sie verwaiste Kanten während anderer Vorgänge träge.

justcoding121
quelle
Für die Adjazenzmatrix entfernt das Entfernen des Scheitelpunkts O (V ^ 2), nicht O (V)
Saurabh
Ja. Wenn Sie jedoch ein Wörterbuch verwenden, um die Array-Indizes zu verfolgen, wird es auf O (V) reduziert. Schauen Sie sich diese RemoveVertex- Implementierung an.
justcoding121