Drei Möglichkeiten zum Speichern eines Diagramms im Speicher: Vor- und Nachteile

Es gibt drei Möglichkeiten, ein Diagramm im Speicher zu speichern:

1. Knoten als Objekte und Kanten als Zeiger
2. Eine Matrix, die alle Kantengewichte zwischen dem nummerierten Knoten x und dem Knoten y enthält
3. Eine Liste der Kanten zwischen nummerierten Knoten

Ich weiß, wie man alle drei schreibt, aber ich bin mir nicht sicher, ob ich an alle Vor- und Nachteile der einzelnen gedacht habe.

Welche Vor- und Nachteile hat jede dieser Möglichkeiten, ein Diagramm im Speicher zu speichern?

Eine Möglichkeit, diese zu analysieren, besteht in der Speicher- und Zeitkomplexität (abhängig davon, wie Sie auf das Diagramm zugreifen möchten).

Speichern von Knoten als Objekte mit Zeigern aufeinander

• Die Speicherkomplexität für diesen Ansatz ist O (n), da Sie so viele Objekte wie Knoten haben. Die Anzahl der erforderlichen Zeiger (auf Knoten) beträgt bis zu O (n ^ 2), da jedes Knotenobjekt Zeiger für bis zu n Knoten enthalten kann.
• Die zeitliche Komplexität für diese Datenstruktur beträgt O (n) für den Zugriff auf einen bestimmten Knoten.

Speichern einer Matrix von Kantengewichten

• Dies wäre eine Speicherkomplexität von O (n ^ 2) für die Matrix.
• Der Vorteil dieser Datenstruktur besteht darin, dass die zeitliche Komplexität für den Zugriff auf einen bestimmten Knoten O (1) beträgt.

Abhängig davon, welchen Algorithmus Sie im Diagramm ausführen und wie viele Knoten vorhanden sind, müssen Sie eine geeignete Darstellung auswählen.

Noch ein paar Dinge zu beachten:

1. Das Matrixmodell eignet sich leichter für Diagramme mit gewichteten Kanten, indem die Gewichte in der Matrix gespeichert werden. Das Objekt- / Zeigermodell müsste Kantengewichte in einem parallelen Array speichern, was eine Synchronisation mit dem Zeigerarray erfordert.

2. Das Objekt / Zeiger-Modell funktioniert besser mit gerichteten Graphen als mit ungerichteten Graphen, da die Zeiger paarweise gepflegt werden müssten, was zu einer Nicht-Synchronisation führen kann.

Die Objekt-und-Zeiger-Methode leidet, wie einige angemerkt haben, unter Schwierigkeiten bei der Suche, ist jedoch ziemlich natürlich, um beispielsweise binäre Suchbäume zu erstellen, in denen es viele zusätzliche Strukturen gibt.

Ich persönlich liebe Adjazenzmatrizen, weil sie mit Werkzeugen aus der algebraischen Graphentheorie alle Arten von Problemen viel einfacher machen. (Die k-te Potenz der Adjazenzmatrix gibt beispielsweise die Anzahl der Pfade der Länge k vom Scheitelpunkt i zum Scheitelpunkt j an. Fügen Sie eine Identitätsmatrix hinzu, bevor Sie die k-te Potenz verwenden, um die Anzahl der Pfade der Länge <= k zu erhalten. Nehmen Sie einen Rang n-1 Moll des Laplace, um die Anzahl der überspannenden Bäume zu ermitteln ... und so weiter.)

Aber jeder sagt, Adjazenzmatrizen sind speicherintensiv! Sie sind nur zur Hälfte richtig: Sie können dies mit spärlichen Matrizen umgehen, wenn Ihr Diagramm nur wenige Kanten hat. Sparse-Matrix-Datenstrukturen erledigen genau die Aufgabe, nur eine Adjazenzliste zu führen, verfügen jedoch über die gesamte Bandbreite der verfügbaren Standard-Matrixoperationen und bieten Ihnen das Beste aus beiden Welten.

Ich denke, Ihr erstes Beispiel ist etwas mehrdeutig - Knoten als Objekte und Kanten als Zeiger. Sie können diese verfolgen, indem Sie nur einen Zeiger auf einen Stammknoten speichern. In diesem Fall ist der Zugriff auf einen bestimmten Knoten möglicherweise ineffizient (beispielsweise möchten Sie Knoten 4 - wenn das Knotenobjekt nicht bereitgestellt wird, müssen Sie möglicherweise danach suchen). . In diesem Fall verlieren Sie auch Teile des Diagramms, die vom Stammknoten aus nicht erreichbar sind. Ich denke, dies ist der Fall, den f64 rainbow annimmt, wenn er sagt, dass die zeitliche Komplexität für den Zugriff auf einen bestimmten Knoten O (n) ist.

Andernfalls können Sie auch ein Array (oder eine Hashmap) voller Zeiger auf jeden Knoten behalten. Dies ermöglicht O (1) den Zugriff auf einen bestimmten Knoten, erhöht jedoch die Speichernutzung ein wenig. Wenn n die Anzahl der Knoten und e die Anzahl der Kanten ist, wäre die Raumkomplexität dieses Ansatzes O (n + e).

Die Raumkomplexität für den Matrixansatz würde entlang der Linien von O (n ^ 2) liegen (vorausgesetzt, die Kanten sind unidirektional). Wenn Ihr Diagramm spärlich ist, haben Sie viele leere Zellen in Ihrer Matrix. Wenn Ihr Graph jedoch vollständig verbunden ist (e = n ^ 2), ist dies im Vergleich zum ersten Ansatz günstig. Wie RG sagt, kann es bei diesem Ansatz auch zu weniger Cache-Fehlern kommen, wenn Sie die Matrix als einen Speicherblock zuweisen, wodurch das Verfolgen vieler Kanten im Diagramm schneller werden kann.

Der dritte Ansatz ist in den meisten Fällen wahrscheinlich der platzsparendste - O (e) -, würde jedoch das Finden aller Kanten eines bestimmten Knotens zu einer O (e) -Aufgabe machen. Ich kann mir keinen Fall vorstellen, in dem dies sehr nützlich wäre.

Schauen Sie sich die Vergleichstabelle auf Wikipedia an. Es gibt ein ziemlich gutes Verständnis dafür, wann jede Darstellung von Graphen verwendet werden muss.

Es gibt noch eine andere Option: Knoten als Objekte, Kanten auch als Objekte, wobei sich jede Kante gleichzeitig in zwei doppelt verknüpften Listen befindet: Die Liste aller Kanten, die von demselben Knoten ausgehen, und die Liste aller Kanten, die in denselben Knoten gehen .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

Der Speicheraufwand ist groß (2 Zeiger pro Knoten und 6 Zeiger pro Kante), aber Sie erhalten

• O (1) Knoteneinfügung
• O (1) Kanteneinfügung (gegebene Zeiger auf "von" und "zu" Knoten)
• O (1) Kantenlöschung (angesichts des Zeigers)
• Löschen des O (deg (n)) - Knotens (unter Angabe des Zeigers)
• O (deg (n)) Nachbarn eines Knotens finden

Die Struktur kann auch einen eher allgemeinen Graphen darstellen: orientiertes Multigraph mit Schleifen (dh Sie können mehrere unterschiedliche Kanten zwischen denselben beiden Knoten haben, einschließlich mehrerer unterschiedlicher Schleifen - Kanten von x nach x).

Eine ausführlichere Erläuterung dieses Ansatzes finden Sie hier .

Okay, wenn Kanten keine Gewichte haben, kann die Matrix ein binäres Array sein, und die Verwendung von binären Operatoren kann in diesem Fall dazu führen, dass die Dinge sehr, sehr schnell gehen.

Wenn der Graph spärlich ist, scheint die Objekt- / Zeigermethode viel effizienter zu sein. Das Halten des Objekts / der Zeiger in einer Datenstruktur, um sie zu einem einzigen Speicherblock zu überreden, kann ebenfalls ein guter Plan oder eine andere Methode sein, um sie zusammenzuhalten.

Die Adjazenzliste - einfach eine Liste verbundener Knoten - scheint bei weitem die speichereffizienteste, aber wahrscheinlich auch die langsamste zu sein.

Ein gerichtetes Graphen Umkehren ist leicht mit der Matrixdarstellung, und einfach mit dem Adjazenzliste, aber nicht so groß , mit der Objekt / Zeigerdarstellung.