Mit einer Karte für ein Diagramm

Hallo, ich werde über die Implementierung eines Graph-Datenstruktur für einen Kurs (das Diagramm ist nicht Teil der Anforderung, habe ich gewählt, um es verwenden zu nähern, das problem) und mein Erster Gedanke war die Umsetzung mit einem angrenzens Liste, weil das weniger Speicher benötigt, und ich erwarte nicht, dass viele Kanten im Diagramm.

Aber dann fiel es mir auf. Kann ich implementieren einen angrenzens Liste Graphen-Datenstruktur mit Hilfe der Karte (HashMap um genau zu sein). Statt die Liste der Scheitelpunkte ich werde eine Karte von vertices, die dann halten Sie eine kurze Liste von Kanten zu Knoten.

Scheint dies der Weg zu gehen für mich. Aber ich Frage mich, ob jemand sehen kann, irgendwelche Nachteile, die ein student wie ich verpasst haben könnte in der Verwendung eines HashMap? (leider erinnere ich mich sehr müde während wir über HashMaps...also mein wissen von Ihnen ist weniger als alle anderen Datenstrukturen, die ich kenne.) Also ich will sicher sein.

Übrigens bin ich mit Java.

Dies ist ein gerichteter oder ungerichteter graph?
Es hängt wahrscheinlich davon ab, was Sie wollen mit Ihnen zu tun. ???
sorry, ich sollte erwähnt haben, dass, es ist ungerichtete
Eine andere Methode ist die Verwendung einer Objekt-Orientierten Programmiersprache wie Java oder C++, das lassen Sie ein Diagramm erstellen genau die Weise kann man ein Diagramm zeichnen auf Papier! E. g erstellen Sie eine Klasse Vertex enthält eine Liste von Zeiger auf andere Knoten. Sie können erstellen Sie eine vertex-und link-mehr-Eckpunkte, vertex, und so weiter.

InformationsquelleAutor Ethan | 2012-08-30

9

Die zwei primären Methoden für die Darstellung eines Graphen sind:
- mit der Nachbarschaft-Liste (wie Sie bereits erwähnt)
- mit der Nachbarschaft-matrix
Weil Sie nicht haben, zu viele Kanten (d.h. die matrix des angrenzens, der Ihre Graphen spärlich), ich denke, Ihre Entscheidung zu verwenden, die Liste anstelle der matrix ist eine gute, da, wie du schon sagtest, es wird ja weniger Platz da kein Raum verschwendet wird, stellen die fehlenden Kanten. Außerdem Map Ansatz scheint logisch zu sein, so können Sie die Zuordnung der einzelnen Node Ihrer Grafik, um die Liste der Nodes an die es angeschlossen ist. Eine andere alternative wäre, jeden Node Objekt enthalten, wie ein Datenfeld aus der Liste der Knoten, an den er angeschlossen ist. Ich denke, diese beiden Ansätze könnte gut funktionieren. Hab ich fasste es unten.

Ersten Ansatz (behalten Sie die Karte):
```
Map<Node, Node[]> graph = new HashMap<Node, Node[]>();
```
Zweite Ansatz (Daten integriert Node Klasse):
```
public class Node {
    private Node[] adjacentNodes;
    public Node(Node[] nodes) { adjacentNodes = nodes; }
    public Node[] adjacentNodes() { return adjacentNodes; }
}
```
Danke für die info =D
Und wie viel Speicher hat es (im ersten Ansatz) verwenden?

InformationsquelleAutor arshajii
4

Graphen sind traditionell vertreten, entweder über ein angrenzens Liste oder eine Nachbarschaft-matrix (es gibt auch andere Möglichkeiten, die optimiert sind für bestimmte Grafik-Formate, wie zum Beispiel, wenn die Knoten-id ' s sind beschriftet, die sequentiell und/oder kennen Sie die Anzahl von Knoten/Kanten, vor der Zeit, aber ich werde nicht in diese zu bekommen).

Kommissionierung zwischen einem angrenzens Liste und eine Nachbarschaft-matrix hängt von Ihren Bedürfnissen ab. Klar, ein Nachbarschaft-matrix wird mehr Platz als ein angrenzens Liste ("matrix" wird immer (# Knoten)^2 in der Erwägung, dass eine Liste nehmen (Anzahl der Knoten + Anzahl der Kanten), aber wenn Ihr graph ist die "kleine", dann macht nicht wirklich einen Unterschied machen.

Andere Sorge ist, wie viele Kanten, die Sie haben (ist Ihr graph spärlich oder dicht)? Finden Sie die Dichte Ihres Diagramms, indem die Anzahl der Kanten, die Sie haben und teilen es durch:

n(n-1) /2

Wobei "n" die Anzahl der Knoten des Graphen. Die obige Gleichung findet, die Gesamtanzahl der möglichen Kanten in einem "n" Knoten-UNGERICHTETE Graphen. Wenn der graph gerichtet ist, entfernen Sie die "/2".

Etwas anderes zu denken ist, wenn effiziente edge-Mitgliedschaft ist wichtig. Ein angrenzens Liste erkennen kann edge Mitgliedschaft schnell (O(1)), da es nur ein array-lookup - für eine Nachbarschaft-Liste, wenn die "Liste" gespeichert ist, als etwas anderes als ein HashSet es wird viel langsamer, da Sie sich durch die gesamte edgelist. Oder vielleicht halten Sie die edgelist - sortiert-und Sie können nur tun, eine binäre Suche, aber dann edge insertion dauert länger. Vielleicht ist Ihr graph ist sehr spärlich, und Nachbarschaft-matrix ist die Verwendung von zu viel Speicher, so dass Sie ein Nähe-Liste. Viele Dinge zu denken.

Gibt es viel mehr betrifft, kann sich auf Ihr Projekt, die ich nur ein paar aufzulisten.

Im Allgemeinen, vorausgesetzt, Ihr graph ist nicht sehr Komplex oder "groß" (im Sinne von Millionen von Knoten), einer HashMap wo der Schlüssel ist die Knoten-ID und der Wert ist ein Set oder eine andere Sammlung von Knoten-IDS angibt, die Nachbarn der wichtigsten Knoten ist in Ordnung, ich habe dies getan, für 400.000+ node-Graphen auf eine 8 GB Maschine. Ein HashMap basierte Implementierung wird wahrscheinlich am einfachsten zu implementieren.

Ich hab mich schon entschieden, ich werde mit einem Satz in Verbindung mit meiner Grafik, ich bin froh, dass Sie erwähnt es aber. Vielen Dank für die gute info! Klingt nicht, als ich nichts übersehen habe =D

InformationsquelleAutor adelbertc

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.