c++ - representacion - ¿Qué es una lista de adyacencia y cómo codifica uno?

lista de adyacencia python

Question

Aquí hay una publicación SO de una lista de adyacencia. Sin embargo, no veo diferencia de una lista de enlaces únicos? También aquí hay un artículo de wikipedia que dice que son todos los bordes (de un gráfico, tipo matemático discreto) en una lista que es bastante amplia, si tengo un gráfico, que no es un gráfico de ruta. ¿Cómo codigo una lista de adyacencia?

Answer 1

Entonces, Boost incluye un contenedor adjacency_list como parte de boost :: graph.

En general, y la lista de adyacencia es más que una lista individualmente vinculada. Describe las conexiones directas (potencialmente, de una dirección dada) de cualquier vértice a otros vértices en el gráfico.

El boost docs proporciona algunos ejemplos básicos, con imágenes.

Answer 2

struct Node {
    std::vector<std::shared_ptr<Node>> Neighbors;
};
struct AdjacencyList{
    std::vector<std::shared_ptr<Node>> Nodes;
};

AdjacencyList contiene una matriz de todos los Node , y cada Node tiene enlaces a todos los otros Node de la lista. Técnicamente, no se requiere la clase std::shared_ptr<Node> root; , todo lo que se requiere es una std::shared_ptr<Node> root; , pero tener una AdjacencyList con un vector hace que iterar sobre ellos, y muchas otras cosas, sea mucho más fácil.

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

AdjacencyList mantiene punteros a A , B , C , D , E y F
A tiene punteros a B y C
B tiene punteros a A D y E
C tiene punteros a A
D tiene punteros a B y E E tiene punteros a B y D
F tiene punteros a ningún otro nodo.

AdjacencyList debe contener punteros y no valores de Node , o cuando cambie el tamaño, todos los punteros Neighbors se invalidarán.

Answer 3

Un ejemplo simple: supongamos que tiene un Vértice de tipo Vertex . Ellos su gráfico consiste en un conjunto de vértices, que puede implementar como:

std::unordered_set<Vertex> vertices;

Ahora, para cada par de vértices entre los cuales hay un borde en su gráfico, necesita registrar ese borde. En una representación de lista de adyacencia, harías un tipo de borde que podría ser un par de vértices, y tu lista de adyacencia podría ser simplemente una lista (o de nuevo un conjunto) de dichos bordes:

typedef std::pair<Vertex, Vertex> Edge;
std::list<Edge> edges_as_list;
std::unordered_set<Edge> edges_as_set;

(Probablemente quiera proporcionar el último conjunto con un comparador no dirigido para el cual (a,b) == (b,a) si tiene un gráfico no dirigido ).

Por otro lado, si quieres hacer una representación de matriz de adyacencia , deberías crear una matriz de bools e indicar qué vértices tienen bordes entre ellos:

bool edges_as_matrix[vertices.size()][vertices.size()]; // `vector` is better
// edges_as_matrix[i][j] = true if there''s an edge

(Para esto necesitaría una manera de enumerar los vértices. En un gráfico no dirigido, la matriz de adyacencia es simétrica, en un gráfico dirigido no tiene por qué serlo).

La representación de la lista es mejor si hay pocos bordes, mientras que la representación de la matriz es mejor si hay muchos bordes.