Comparación de la representación gráfica de objetos con la lista de adyacencia y las representaciones matriciales

81

Actualmente sigo el consejo de Steve Yegge sobre cómo prepararme para una entrevista de programación técnica: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

En su sección de Gráficos, afirma:

Hay tres formas básicas de representar un gráfico en la memoria (objetos y punteros, matriz y lista de adyacencia), y debe familiarizarse con cada representación y sus pros y contras.

Los pros y los contras de las representaciones de listas de adyacencia y matrices se describen en CLRS, pero no he podido encontrar un recurso que los compare con una representación de objeto.

Con solo pensarlo, puedo inferir algo de esto yo mismo, pero me gustaría asegurarme de no haberme perdido algo importante. Si alguien pudiera describir esto de manera exhaustiva, o señalarme un recurso que lo hace, lo agradecería enormemente.

jbeard4
fuente
¿ Qué hay de los gráficos inductivos ? ¿A cuál de las 3 categorías pertenecen?
Erik Kaplun

Respuestas:

94

objetos y punteros

Estas son solo estructuras de datos básicas como Hammar dijo en la otra respuesta, en las Javaque representaría esto con clases como bordes y vértices. Por ejemplo, un borde conecta dos vértices y puede estar dirigido o no dirigido y puede contener un peso. Un vértice puede tener una ID, un nombre, etc. En su mayoría, ambos tienen propiedades adicionales. Entonces puedes construir tu gráfico con ellos como

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30  

Este enfoque se usa comúnmente para implementaciones orientadas a objetos, ya que es más legible y conveniente para usuarios orientados a objetos;).

matriz

Una matriz es simplemente una matriz bidimensional simple. Suponiendo que tiene ID de vértice que se pueden representar como una matriz int como esta:

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

Esto se usa comúnmente para gráficos densos donde es necesario el acceso al índice. Puede representar una estructura ponderada y no dirigida con esto.

lista de adyacencia

Esta es solo una combinación de estructura de datos simple, generalmente la implemento usando un archivo HashMap<Vertex, List<Vertex>>. Similar utilizado puede ser el HashMultimapde Guayaba.

Este enfoque es genial, porque tiene una búsqueda de vértices O (1) (amortizada) y me devuelve una lista de todos los vértices adyacentes a este vértice en particular que exigí.

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

Esto se utiliza para representar gráficos dispersos, si está postulando en Google, debe saber que el webgraph es escaso. Puede tratar con ellos de una manera más escalable utilizando BigTable .

Ah, y por cierto, aquí hay un muy buen resumen de esta publicación con imágenes elegantes;)

Thomas Jungblut
fuente
Este enfoque es genial, debido a que tiene una búsqueda de vértices O (1), esta complejidad es ligeramente incorrecta, en particular es O (1 + alfa) donde alfa = número de ranuras en el mapa hash / número de vértices. Por lo tanto, propongo usar una matriz en lugar de un mapa hash
Timofey
@Tim se amortiza O (1). Su cálculo de complejidad depende en gran medida de la implementación. Vea el javadoc de HashMap( docs.oracle.com/javase/7/docs/api/java/util/HashMap.html ) dice: This implementation provides constant-time performance for the basic operations= O (1) amortizado.
Thomas Jungblut
6
@Tim Creo que todos aquí saben que el acceso a la matriz es más rápido que cualquier HashTableuso. Por lo tanto, no hay necesidad de ser quisquilloso con una pequeña sobrecarga alfa constante que se puede descuidar.
Thomas Jungblut
2
Por favor, no me malinterpretes, no te ofendo buena respuesta, pero tengo la sensación de que tu respuesta puede mejorar, así que ¿por qué no mencionarlo aquí :)
Timofey
2
@Tim Agregué la nota amortizada en la respuesta. Gracias.
Thomas Jungblut
7

Objetos y punteros es en su mayoría lo mismo que la lista de adyacencia, al menos con el propósito de comparar algoritmos que usan estas representaciones.

Comparar

struct Node {
    Node *neighbours[];
};

con

struct Node {
    Node *left;
    Node *right;
};

Puede construir fácilmente la lista de vecinos sobre la marcha en el último caso, si es más fácil trabajar con él que con punteros con nombre.

Hammar
fuente
4

La ventaja de la representación de objetos ( lista de incidencia ) es que dos vértices adyacentes comparten la misma instancia del borde. Esto hace que sea fácil de manipular con datos de bordes no dirigidos (longitud, costo, flujo o incluso dirección). Sin embargo, utiliza memoria adicional para los punteros.

Michal Čizmazia
fuente
5
¿Por qué hay un enlace a la representación de la lista de adyacencia denominada "lista de incidencia"? Probablemente sea mejor usar este algoritmo.com/index.php/Graph_data_structures#Incidence_List
Timofey
1

Otro buen recurso: Khan Academy - "Representación de gráficos"

Además de la lista de adyacencia y la matriz de adyacencia, enumeran "listas de bordes" como un tercer tipo de representación gráfica. Una lista de bordes se puede interpretar como una lista de "objetos de borde" como los de la respuesta de Thomas "objetos y punteros".

Ventaja: podemos almacenar más información sobre el borde (mencionado por Michal)

Desventaja: Es una estructura de datos muy lenta para trabajar:

  • Buscar un borde: O (log e)
  • Eliminar un borde: O (e)
  • Encuentre todos los nodos adyacentes a un nodo dado: O (e)
  • Determine si existe una ruta entre dos nodos: O (e ^ 2)

e = número de aristas

Chris Leung
fuente