Was ist die beste standard-Daten-Struktur zu bauen, ein Graph?

zuerst ich bin Anfänger in c++ und ich bin selbst lernen, also bitte ganz einfach Antworten ...

brauche ich um das Programm einen Graphen, die Knoten enthält jeder Knoten-id und eine Liste von Kanten, jede Kante hat, die andere Knoten-id und die Entfernung

was ich Suche ist was soll ich zum erstellen dieser Grafik wenn man bedenkt, dass ich verwenden möchte, dijkstra-Algorithmus, um die kürzesten Weg bilden einem Punkt zum anderen ... so Suche Leistung sollte das wichtigste denke ich !!

gesucht hab ich viel, und ich bin so verwirrt jetzt

vielen Dank im Voraus für die Hilfe

InformationsquelleAutor Dawnlight | 2011-07-29
  1. 11

    Definieren Sie eine Edge Struktur wie

    struct Edge
{
    int destination;
    int weight;
};

    Und ein Diagramm erstellen, wie

    vector<vector<Edge> > graph;

    Dann Zugriff auf alle Kanten kommt aus der vertex - u Sie so etwas schreiben

    for( int i = 0; i < graph[u].size(); ++i ) {
    Edge edge = graph[u][i];
    //here edge.destination and edge.weight give you some details.
}

    Können Sie dynamisch hinzufügen neuer Kanten, zum Beispiel eine Kante vom vertex 3. bis 7. mit einem Gewicht von 8:

    Edge newEdge;
newEdge.destination = 7;
newEdge.weight = 8;
graph[3].push_back( newEdge );

    etc.

    Für ungerichtete Graphen sollte man nicht vergessen, hinzuzufügen, die symmetrischen Rand, natürlich.

    Sollte dies ok.

    Bearbeiten
    Die Wahl der base Container (std::vector, std::list, std::map) ist abhängig vom Anwendungsfall, z.B. was machst du mit den Graphen oft: hinzufügen/entfernen von vertices/edges, einfach durchqueren. Sobald Sie Ihr Diagramm erstellt, entweder std::list oder std::vector ist gleich gut für den Dijkstra, std::vector ein bisschen schneller durch sequentielle Zugriffsmuster der Entspannung Bühne.

    • diese Antwort, die ich schon kenne .. ich Frage, ob der Vektor das beste, was zu verwenden .. für die Leistung ?? und welche ist die bessere Karte oder vecotrs ??
    • danke für den edit-es klärt die Sache auf, aber wenn ich will, um die Sortierung der Knoten des Graphen und die Kanten nach id einen heap Sortieren .. wird dies damit es schneller geht ?? und wenn ja .. was soll ich tun so etwas ??
    • Dies sind die Allgemeinen Fragen zur Programmierung unabhängig von Graphen, richtig? Sollten Sie Fragen, eine eigene Frage (die erste Suche nach aber)
    • sollte ich Programm Diagramm nach dem, was ich will, es zu bauen, für ... also muss ich es umsetzen dijkstra effiecintly setzen in mir, die Grafik große Anzahl von Knoten und Kanten
    • wenn Sie brauchen, Graphen zu Lesen, von einem Ort, führen dijkstra und Ausgabe der Ergebnisse, Vektor von Vektoren ist perfekt.
    • danke @unkulunkulu werde ich Vektoren verwenden 🙂
    • Wenn Sie wollen, um Leistung zu Programmieren, müssen Sie in der Regel genau diesen Containern, in der Reihenfolge der Häufigkeit: std::vector<>, std::unordered_map<>, und std::unordered_set<>. Alle anderen Container sind besser als von einem der drei in jedem Fall verwenden, Sie müssen nur richtig eingesetzt werden.

    InformationsquelleAutor unkulunkulu
  2. 0

    einen Graphen, die Knoten enthält jeder Knoten-id und eine Liste von Kanten, jede Kante hat, die andere Knoten-id und die Entfernung

    Wenn wir Bedenken, dass jede node-id als index. Wir ziehen können eine nxn-matrix der Kanten wie folgt.

    Dies kann Ihnen helfen, ziehen die Grafik mit Ecken und Kanten.

         [0][1][2][3]

[0] | 1  0  0  0|
[1] | 0  0  1  0|
[2] | 1  0  0  1|
[3] | 0  0  1  0|

    Also ein 2D-array ist eine gute Darstellung der matrix.

    int maxtrix[4][4] = new int[4][4];
    • Dies ist nicht eine performante Lösung, wenn die matrix Dünn, die Sie übernehmen müssen, wenn der Dijkstra-Algorithmus ins Spiel kommt. Die Leistung verloren, die Suche nach nicht-null Kanten, die Weg führt von einem gegebenen Knoten.
    • Danke für den Kommentar. Falls die Daten verwandelt sich in eine sparse-matrix, müssen Wir für eine besser geeignet-Algorithmus oder verwenden Sie die Yale-format.
    InformationsquelleAutor Sorter
  3. -1

    Ich persönlich würde verwenden eine std::map<Node*, std::set<Node*> >. Dies ist sehr nützlich, weil jedes mal, wenn Sie auf einem Knoten können Sie schnell herausfinden, welche Knoten, die Knoten verbunden ist. Es ist auch wirklich einfach zu Iteration über alle Knoten, die, wenn Sie benötigen. Wenn Sie brauchen, um GEWICHTE auf den Kanten, die Sie nutzen könnten std::map<Node*, std::set< std::pair<int, Node*> > >. Dies gibt eine wesentlich bessere performance als die Verwendung von Vektoren, insbesondere für große Graphen.

    • std::vector<> übertrifft std::map<> jederzeit std::vector<> übertrifft std::set<> wenn Sie nicht brauchen, zu bestellen. Beide std::map<> und std::set<> verlassen Sie sich auf Bäumen intern, und haben somit viel höhere Zuweisung overhead beim breiter Streuung der Daten zu. std::vector<> verwendet einen zusammenhängenden array intern, und ist somit 1. Speicher effizient, 2. cache-effiziente 3-Allokation effiziente, 4. prefetching freundlich. Wirklich, std::map<> und std::set werden nicht ein Teil der optimizer toolbox.
    • Ich glaube wirklich, dass die das tun, komplexe algorithmen in großen Graphen mit vielen access std::map<> und std::set<> würde gewinnen, weil der untere exponentielle Zugriffszeit. Ich wäre offen zu sehen-benchmarks, die beweisen, mich falsch aber.
    • Nein, sicherlich nicht: Zugriffszeit std::vector<> ist ein single-pointer-dereference-Bedienung auf der Maschinen-Ebene, während die beiden std::map<> und std::set<> müssen durch einen Baum, was bedeutet, dass log(n) - Zeiger-Dereferenzierung Operationen. Besonders für große Daten-sets, wo die Bäume sind tief. Sie können nicht schlagen die Leistung von einer Byte-array im Speicher.
    • Ok, ja, natürlich-Vektor ist besser, wenn Sie wissen, der index, was Sie suchen. Ich dachte da eher an den Fall, wenn Sie nicht, dann schauen schlimmer ist für Vektoren.
    InformationsquelleAutor setholopolus
Schreibe einen Kommentar