Implementierung eines angrenzens Liste graph-Darstellung

Ich habe gerade angefangen mit der Graphentheorie. Ich kann nicht herausfinden, wie man code angrenzens Liste mit verknüpften Listen. zum Beispiel, wenn ich in diesem Graphen (ungerichtete):

A--------B
|       /|\
|      / | \  
|     /  |  \
|    /   |   \
|   /    |    \
|  /     |     \
| /      |      \
C        E-------D

Wie code ich es? Ich weiß, wie es zu tun mit Nähe matrix, aber wie es code mit angrenzens Liste und verknüpfte Listen (c++)?

InformationsquelleAutor Somebody | 2013-01-03
  1. 14

    Eines angrenzens Liste ist nur ein Vektor/array von Listen. Jedes element im Diagramm ist ein element im array, und eine Kante Hinzugefügt wird, ist es angrenzens Liste. So sieht es etwas aus wie:

    Ein -> {B, C}

    B -> {A, C, D, E}

    C -> {A, B}

    D -> {B, E}

    E -> {B, D}

    Also beginnen wir mit etwas, das wie std::vector<std::list<vertex>>. Jedoch, können wir tun besser als dieses, weil verticies sind einzigartig, daher können wir nutzen eine map. Außerdem, ein vertex kann nur erscheinen in einem edge-Liste einmal, damit wir es ändern zu std::map<vertex, std::set<vertex>>.

    So, mit zu beginnen, so etwas wie:

    struct vertex
{
   //
};

class undirected_graph
{
private:
    std::map<vertex, std::set<vertex>> graph_container;
public:
    void add_vertex(const vertex& v) { //add a vertex to the map }
    void add_edge(const vertex& v, const vertex& u) { //look up vertex in map and add to the vertex adjacency list }
    //Other methods
    //...
 };
    • Aus Wikipedia: "In der Graphentheorie eine angrenzens Liste ist die Darstellung der alle Kanten oder Bögen im Graphen als Liste." Was Sie implementiert haben, ist vielleicht eine Optimierung, aber das grundlegende Konzept ist ein bisschen verdeckt.
    • mit Vektoren ist auch eine gute option, richtig?
    • Sicher. Wenn Sie versuchen, zu implementieren, die diese zum ersten mal verwenden, was am einfachsten ist.
    • ist-Vektoren, die eine effiziente option?
    • Naja, der ganze Punkt des angrenzens Listen vs Nachbarschaft matricies ist, dass Sie mehr Speicher effizient für Graphen, die nicht zu viele Kanten. Die map/set Umsetzung wird wahrscheinlich schneller sein, aber für alle Grafiken, die nicht Recht groß, der Unterschied wird vermutlich minimal sein.
    • mit std::map für angrenzens Liste führt zu O(|V|*log(|V|)+|E|) Komplexität für die bfs/dfs-traversal), wobei |V|,|E|, sind die Größe von Ecken und Kanten. Daher für sparse matrix, es führt zu mehr Zeit, Komplexität.
    • Höhere Komplexität im Vergleich zu was? Wenn du meinst, wie im Vergleich zu einer undordered_map, dann ja, Sie können es reduzieren auf O(|V| + |E|) (da amortisiert O(1) lookup).

    InformationsquelleAutor Yuushi
  2. 3

    Eines angrenzens Liste wäre nur ein Satz von Objekten, die die Kanten des Graphen.

    struct edge {
    node *nodes[2];

    edge( node *a, node *b ) {
        if ( a < b ) { //define canonical order of edges for undirected graph
            nodes[0] = a;
            nodes[1] = b;
        } else {
            nodes[0] = b;
            nodes[1] = a;
        }
    }
};

    Einer verknüpften Liste, klingt nicht besonders praktisch; in der Regel würden Sie definieren eine Reihenfolge von Kanten und legen Sie Sie in einem std::set oder std::map.

    bool operator< ( edge const &lhs, edge const &rhs ) {
    if ( lhs.nodes[0] < rhs.nodes[0] ) return true;
    if ( rhs.nodes[0] < lhs.nodes[0] ) return false;
    return lhs.nodes[1] < rhs.nodes[1];
}

typedef std::set< edge > graph;

    Gibt es viele Möglichkeiten, dies zu tun, ist es schwer etwas empfehlen, ohne zu wissen, was Sie beabsichtigen zu tun mit der Grafik.

    InformationsquelleAutor Potatoswatter
Schreibe einen Kommentar