___ qstnhdr ___ Erstellung einer Adjazenzliste in C ++ für einen gerichteten Graphen
___ answer22120857 ___
Ich schlage vor, dass Sie in der Knotenstruktur die Adjazenzliste hinzufügen
Und definieren Sie die Graphenstruktur als Liste der Knoten anstelle der Liste der Adjazenzlisten:)
%Vor%
___ answer46552391 ___
Mein Ansatz wäre, eine Hash-Map zu verwenden, um die Liste der Knoten im Graphen zu speichern
%Vor%
Die Karte übernimmt die Knoten-ID als Schlüssel und den Knoten selbst als Wert. Auf diese Weise können Sie in konstanter Zeit nach einem Knoten im Diagramm suchen.
Der Knoten enthält die Adjazenzliste, in diesem Fall als c ++ 11-Vektor. Es könnte auch eine verkettete Liste sein, obwohl ich für diesen Anwendungsfall keinen Unterschied in der Effizienz sehen würde. Vielleicht wäre die Liste besser, wenn du es irgendwie sortiert halten möchtest.
%Vor%
Bei diesem Ansatz müssen Sie die Adjazenzliste durchgehen und dann die Karte auf der ID durchsuchen, um den Knoten zu erhalten.
Alternativ könnten Sie einen Vektor von Zeigern zu den Nachbarknoten selbst haben. Dadurch erhalten Sie direkten Zugriff auf die Nachbarknoten. Sie können jedoch keine Karte verwenden, um alle Knoten im Diagramm zu behalten, und Sie verlieren die Möglichkeit, Einträge in Ihrem Diagramm einfach zu suchen.
Wie Sie sehen können, müssen Sie bei der Implementierung eines Diagramms eine Reihe von Trade-Off-Entscheidungen treffen. Dies hängt von Ihren Anwendungsfällen ab.
___ tag123c ___ C ++ ist eine universelle Programmiersprache. Es wurde ursprünglich als Erweiterung von C entworfen und behält eine ähnliche Syntax, ist aber jetzt eine komplett andere Sprache. Verwenden Sie dieses Tag für Fragen zu Code, der mit einem C ++ - Compiler kompiliert werden soll.
___ tag123graph ___ Graph bezieht sich auf eine Grafik (z. B. ein Diagramm oder ein Diagramm), die die Beziehung zwischen zwei oder mehr Variablen anzeigt.
Verwenden Sie für die diskrete mathematische Struktur, die aus Vertices und Kanten besteht, das Graph-Theorie-Tag.
___ answer40318771 ___
Ich würde den allgemeineren und einfacheren Ansatz der Verwendung von Vektoren und Paaren empfehlen:
#einschließen
#include
%Vor%
Oder Alias-Stil (& gt; = C ++ 11):
%Vor%
Von hier:
mit Vektor und Paaren (aus Tejas Antwort)
Für weitere Informationen können Sie sich auf eine sehr gute Zusammenfassung von topcoder beziehen:
Power up C ++ mit STL
___ antwort22121060 ___
Das mag kein sehr allgemeiner Ansatz sein, aber so handle ich in den meisten Fällen mit der Adjazenzliste. C ++ hat eine STL-Bibliothek, die eine Datenstruktur für die verknüpfte Liste namens list unterstützt.
Angenommen, Sie haben N Knoten im Diagramm, erstellen Sie eine verknüpfte Liste für jeden Knoten.
%Vor%
Jetzt stellen graph[i] die Nachbarn von Knoten i dar. Führe für jede Kante i bis j
aus
%Vor%
Der beste Komfort ist die Behandlung von Zeigern, so dass Fehler bei Segmentationsfehlern vermieden werden.
Für mehr Referenz Ссылка
___ tag123adjacenylist ___ Eine Adjazenzliste ist eine Repräsentation eines Graphen, eine Sammlung von ungeordneten Listen, eine für jeden Knoten im Graphen.
___ answer22121090 ___
Sie können einen Vektor im Knoten als Adjazenzliste verwenden.
%Vor%
Wenn das Diagramm zum Zeitpunkt der Kompilierung bekannt ist, können Sie das Array verwenden, aber es ist "ein wenig" etwas härter. Wenn Sie nur die Größe des Graphen kennen (zur Kompilierzeit), können Sie so etwas machen.
%Vor%
Um einen Nachbarn hinzuzufügen, machen Sie so etwas (vergessen Sie nicht die Nummerierung von Null):
%Vor%
Natürlich können Sie eine No-Pointer-Adjazenzliste erstellen und "über" einer Tabelle arbeiten. Dann hast du %code% im Knoten und drückst die Nummer des Nachbarn. Mit beiden Darstellungen des Graphen können Sie alle Algorithmen realisieren, die die Adjazenzliste verwenden.
Und schließlich, könnte ich hinzufügen. Einige verwenden anstelle eines Vektors eine Liste , da die Entfernung in O (1) Zeit. Fehler. Für die meisten Algorithmen ist die Reihenfolge in der Adjazenzliste nicht wichtig. Sie können also jedes Element in O (1) aus dem Vektor löschen. Tauschen Sie es einfach mit dem letzten Element aus, pop_back ist O (1) Komplexität. So ähnlich:
%Vor%
Spezifisches Beispiel (Sie haben Vektor im Knoten, C ++ 11 (!)):
%Vor%
Ich glaube, es ist klar. Von %code% können Sie zu %code% , von %code% zu %code% und zu sich selbst gehen und (wie zB) von %code% zu %code% . Es ist ein gerichteter Graph. Wenn Sie ungerichtet sind, sollten Sie die Adressen der Nachbarknoten hinzufügen. Sie können Zahlen anstelle von Zeigern verwenden. %code% in %code% und Zurückdrücken von Zahlen, keine Adressen.
Wie wir wissen, müssen Sie keine Zeiger verwenden. Hier ist ein Beispiel dafür.
Wenn sich die Anzahl der Scheitelpunkte ändern kann, können Sie den Vektor der Knoten ( %code% ) anstatt des Arrays verwenden, und nur Größenänderung . Der Rest bleibt unverändert. Zum Beispiel:
%Vor%
Aber Sie können nicht einen Knoten löschen, dies verletzt die Nummerierung! Wenn Sie etwas löschen möchten, sollten Sie die Liste ( %code% ) der Zeiger verwenden. Andernfalls müssen Sie nicht vorhandene Scheitelpunkte beibehalten. Hier ist die Reihenfolge wichtig!
In Bezug auf die Zeile %code% ist es sicher mit Graphen ohne Zeiger. Wenn Sie Zeiger verwenden möchten, sollten Sie nicht die Größe des Diagramms ändern.
Sie können die Adresse einiger Knoten versehentlich ändern, indem Sie den Scheitelpunkt hinzufügen, wenn %code% an einen neuen Platz (nicht im Speicher) kopiert wird.
Eine Möglichkeit, damit umzugehen, ist die Reservierung , obwohl Sie die maximale Größe kennen müssen der Grafik! Aber tatsächlich ermutige ich Sie, %code% nicht zu verwenden, um Scheitelpunkte zu behalten, wenn Sie Zeiger verwenden. Wenn Sie die Implementierung nicht kennen, könnte sicherer das Self-Memory-Management sein (intelligente Zeiger zB shared_ptr oder nur neu ).
%Vor%
Die Verwendung von %code% als Adjazenzliste ist immer fein ! Es gibt keine Möglichkeit, die Adresse des Knotens zu ändern.
___ qstntxt ___
Hallo alle :) Heute verfeinere ich meine Fähigkeiten in Graphentheorie und Datenstrukturen. Ich habe mich entschieden, ein kleines Projekt in C ++ zu machen, weil ich seit einiger Zeit in C ++ arbeite.
Ich möchte eine Adjazenzliste für einen gerichteten Graphen erstellen. Mit anderen Worten, etwas, was wie folgt aussieht:
%Vor%
Dies wäre ein gerichteter Graph mit V0 (Vertex 0) mit einer Kante zu V1 und V3, V1 mit einer Kante zu V2 und V2 mit einer Kante zu V4, wie folgt:
%Vor%
Ich weiß, dass ich dafür eine Adjazenzliste in C ++ erstellen muss. Eine Adjazenzliste ist im Grunde ein Array von verknüpften Listen . Okay, lass uns einen Pseudo-C ++ - Code sehen:
%Vor%
Wie Sie sehen können, ist dieser Pseudocode derzeit weit von der Marke entfernt. Und darum wollte ich etwas Hilfe - Zeiger und Strukturen in C ++ waren nie meine Stärke. Zuallererst kümmert sich das um die Scheitelpunkte, auf die ein Scheitelpunkt zeigt - aber was ist mit dem Scheitelpunkt selbst? Wie kann ich diesen Eckpunkt verfolgen? Wenn ich über das Array schleife, ist es nicht gut, nur zu wissen, auf welche Scheitelpunkte verwiesen wird, anstatt zu wissen, welche Punkte für sie sind. Das erste Element in jeder Liste sollte wahrscheinlich dieser Scheitelpunkt sein, und dann sind die Elemente danach die Scheitelpunkte, auf die er zeigt. Aber wie kann ich auf dieses erste Element der Liste in meinem Hauptprogramm zugreifen? (Entschuldigung, wenn das verworren oder verwirrend ist, würde ich gerne umformulieren).
Ich würde gerne in der Lage sein, diese Adjazenzliste zu durchlaufen, um einige coole Dinge mit Graphen zu machen. Um beispielsweise einige Graphentheoriealgorithmen (Sortierungen, kürzeste Pfade usw.) unter Verwendung der Adjazenzlisten-Darstellung zu implementieren.
(Außerdem hatte ich eine Frage zu der Adjazenzliste. Was ist anders als nur eine Liste von Arrays zu verwenden? Warum kann ich nicht einfach eine Liste mit einem Array für jedes Element in der Liste haben?)
___