Vergleich der Objektdiagrammdarstellung mit der Adjazenzliste und den Matrixdarstellungen

81

Ich folge derzeit Steve Yegges Ratschlägen zur Vorbereitung eines technischen Programmierinterviews: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

In seinem Abschnitt über Grafiken stellt er fest:

Es gibt drei grundlegende Möglichkeiten, ein Diagramm im Speicher darzustellen (Objekte und Zeiger, Matrix und Adjazenzliste), und Sie sollten sich mit jeder Darstellung und ihren Vor- und Nachteilen vertraut machen.

Die Vor- und Nachteile von Matrix- und Adjazenzlistendarstellungen sind in CLRS beschrieben, aber ich konnte keine Ressource finden, die diese mit einer Objektdarstellung vergleicht.

Wenn ich nur darüber nachdenke, kann ich selbst auf etwas davon schließen, aber ich möchte sicherstellen, dass ich etwas Wichtiges nicht verpasst habe. Wenn jemand dies umfassend beschreiben oder mich auf eine Ressource verweisen könnte, die dies tut, würde ich es sehr schätzen.

algorithm graph graph-algorithm jbeard4
quelle
Wie wäre es mit induktiven Graphen - unter welche der drei Kategorien fallen diese?
Erik Kaplun

Antworten:

93

Objekte und Zeiger

Dies sind nur grundlegende Datenstrukturen, wie Hammar in der anderen Antwort sagte. JavaSie würden dies mit Klassen wie Kanten und Eckpunkten darstellen. Beispielsweise verbindet eine Kante zwei Eckpunkte und kann entweder gerichtet oder ungerichtet sein und ein Gewicht enthalten. Ein Scheitelpunkt kann eine ID, einen Namen usw. haben. Meistens haben beide zusätzliche Eigenschaften. So können Sie Ihr Diagramm mit ihnen wie erstellen

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30

Dieser Ansatz wird üblicherweise für objektorientierte Implementierungen verwendet, da er für objektorientierte Benutzer lesbarer und bequemer ist;).

Matrix

Eine Matrix ist nur ein einfaches zweidimensionales Array. Angenommen, Sie haben Scheitelpunkt-IDs, die wie folgt als int-Array dargestellt werden können:

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

Dies wird häufig für dichte Diagramme verwendet, bei denen ein Indexzugriff erforderlich ist. Damit können Sie eine ungerichtete und gewichtete Struktur darstellen.

Adjazenzliste

Dies ist nur ein einfacher Datenstruktur-Mix, den ich normalerweise mit einem implementiere HashMap<Vertex, List<Vertex>>. Ähnlich verwendet kann das HashMultimapin Guave sein.

Dieser Ansatz ist cool, da Sie eine O (1) (amortisierte) Scheitelpunktsuche haben und mir eine Liste aller benachbarten Scheitelpunkte zu diesem bestimmten Scheitelpunkt zurückgeben, den ich angefordert habe. 

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

Dies wird zur Darstellung spärlicher Diagramme verwendet. Wenn Sie sich bei Google bewerben, sollten Sie wissen, dass der Webgraph spärlich ist. Mit einem BigTable können Sie skalierbarer mit ihnen umgehen .

Oh und übrigens, hier ist eine sehr gute Zusammenfassung dieses Beitrags mit ausgefallenen Bildern;)

Thomas Jungblut
quelle
Dieser Ansatz ist cool, da Sie eine O (1) -Scheitelpunktsuche haben. Diese Komplexität ist etwas falsch. Insbesondere ist es O (1 + Alpha), wobei Alpha = Anzahl der Slots in der Hash-Map / Anzahl der Scheitelpunkte. Daher schlage ich vor, Array anstelle von Hash-Map zu verwenden
Timofey
@Tim ist es O (1) amortisiert. Ihre Komplexitätsberechnung hängt stark von der Implementierung ab. Siehe das Javadoc von HashMap( docs.oracle.com/javase/7/docs/api/java/util/HashMap.html ), in dem steht: This implementation provides constant-time performance for the basic operations= O (1) amortisiert.
Thomas Jungblut
6
@ Tim Ich denke, jeder hier weiß, dass der Array-Zugriff schneller ist als jede HashTableNutzung. Sie müssen also nicht mit einem kleinen konstanten Alpha-Overhead herumpicken, der vernachlässigt werden kann.
Thomas Jungblut
2
Bitte versteh mich nicht falsch, ich beleidige dich nicht nett, aber ich habe das Gefühl, dass deine Antwort verbessert werden könnte, also warum nicht hier erwähnen :)
Timofey
2
@Tim Ich habe die amortisierte Notiz in die Antwort eingefügt. Vielen Dank.
Thomas Jungblut
7

Objekte und Zeiger entsprechen größtenteils der Adjazenzliste, zumindest um Algorithmen zu vergleichen, die diese Darstellungen verwenden.

Vergleichen Sie

struct Node {
    Node *neighbours[];
};

mit

struct Node {
    Node *left;
    Node *right;
};

Im letzteren Fall können Sie die Liste der Nachbarn einfach im laufenden Betrieb erstellen, wenn die Arbeit mit benannten Zeigern einfacher ist.

Hammar
quelle
4

Vorteil der Objektdarstellung ( Inzidenzliste ) ist, dass zwei benachbarte Eckpunkte dieselbe Instanz der Kante teilen. Dies erleichtert die Bearbeitung mit ungerichteten Kantendaten (Länge, Kosten, Durchfluss oder sogar Richtung). Es wird jedoch zusätzlicher Speicher für Zeiger verwendet.

Michal Čizmazia
quelle
5
Warum gibt es einen Link zur Darstellung der Adjazenzliste mit dem Namen "Inzidenzliste"? Wahrscheinlich ist es besser, diesen einen algorithmist.com/index.php/Graph_data_structures#Incidence_List
Timofey
1

Eine weitere gute Ressource: Khan Academy - "Representing Graphs"

Neben der Adjazenzliste und der Adjazenzmatrix werden "Kantenlisten" als dritte Art der Diagrammdarstellung aufgeführt. Eine Kantenliste könnte als Liste von "Kantenobjekten" interpretiert werden, wie sie in Thomas 'Antwort "Objekte und Zeiger" enthalten sind.

Vorteil: Wir können weitere Informationen über die Kante speichern (von Michal erwähnt)

Nachteil: Es ist eine sehr langsame Datenstruktur, mit der man arbeiten kann:

  • Suchen Sie eine Kante: O (log e)
  • Entfernen Sie eine Kante: O (e)
  • Finden Sie alle Knoten neben einem bestimmten Knoten: O (e)
  • Bestimmen Sie, ob zwischen zwei Knoten ein Pfad existiert: O (e ^ 2)

e = Anzahl der Kanten

Chris Leung
quelle