Implementierung einer Adjazenzliste Graphendarstellung

Question

Ich habe gerade mit der Graphentheorie begonnen. Ich kann nicht herausfinden, wie man die Adjazenzliste mithilfe von verketteten Listen codiert. Zum Beispiel, wenn ich dieses Diagramm (ungerichtet) habe:

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

Wie kann ich es kodieren? Ich weiß, wie man es mit der Adjazenzmatrix macht, aber wie man es mit Adjazenzliste und verknüpften Listen (C++) programmiert?

Answer 1

Eine Adjazenzliste ist nur ein Vektor/Array von Listen. Jedes Element im Diagramm ist ein Element im Array, und jede Kante wird zur Adjazenzliste hinzugefügt. So sieht es so etwas wie:

A -> {B, C}

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

C -> {A, B}

D -> {B, E}

E -> {B, D}

So beginnen wir mit so etwas wie std::vector<std::list<vertex>>. Allerdings können wir es besser machen, weil die Vertices einzigartig sind, daher können wir eine map verwenden. Darüber hinaus kann ein Eckpunkt nur einmal in einer Kantenliste angezeigt werden, sodass wir ihn in std::map<vertex, std::set<vertex>> ändern.

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 
    //... 
}; 

Answer 2

Eine Adjazenzliste wäre nur eine Gruppe von Objekten, die die Kanten des Graphen darstellen.

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; 
     } 
    } 
}; 

Eine verkettete Liste klingt nicht besonders praktisch; Normalerweise würden Sie eine Reihenfolge der Kanten definieren und sie in eine std::set oder std::map setzen.

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; 

Es gibt viele Möglichkeiten, dies zu tun, ist es schwer, etwas zu mehr empfehlen, ohne zu wissen, was Sie mit dem Diagramm zu tun beabsichtigen.