algorithm - siguiente - representacion matricial de grafos

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

Question

Actualmente estoy siguiendo los consejos de Steve Yegge sobre cómo preparar una entrevista de programación técnica: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

En su sección sobre Gráficos, él declara:

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 sus contras.

Las ventajas y desventajas de las representaciones de listas de matriz y adyacencia se describen en CLRS, pero no he podido encontrar un recurso que las compare con una representación de objetos.

Solo por pensarlo, puedo inferir algo de esto yo mismo, pero me gustaría asegurarme de no haberme perdido algo importante. Si alguien pudiera describir esto exhaustivamente, o señalarme un recurso que lo haga, lo agradecería enormemente.

Answer 1

La ventaja de la representación del objeto ( lista de incidencia ) es que dos vértices adyacentes comparten la misma instancia del borde. Esto facilita la manipulación con datos de borde no dirigidos (longitud, costo, flujo o incluso dirección). Sin embargo, utiliza memoria extra para los punteros.

Answer 2

Los objetos y punteros son 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 ellos que con los punteros nombrados.

Answer 3

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

Además de la lista de adyacencia y la matriz de adyacencia, listan "listas de bordes" como un tercer tipo de representación gráfica. Una lista de bordes podría interpretarse como una lista de "objetos de borde" como los que figuran en la respuesta de "objetos y punteros" de Thomas.

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

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

• Buscar una ventaja: 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 bordes

Answer 4

objetos y punteros

Estas son solo estructuras de datos básicas, como dijo hammar en la otra respuesta, en Java representarías esto con clases como bordes y vértices. Por ejemplo, un borde conecta dos vértices y puede ser dirigido o no dirigido y puede contener un peso. Un vértice puede tener una ID, un nombre, etc. Principalmente ambos tienen propiedades adicionales. Entonces puedes construir tu gráfica 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 fácil de leer y conveniente para usuarios orientados a objetos;).

matriz

Una matriz es solo una simple matriz bidimensional. 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 acceder a índices. Puede representar una estructura un / dirigida y ponderada con esto.

lista de adyacencia

Esta es solo una combinación de estructura de datos simple, generalmente implemento esto usando un HashMap<Vertex, List<Vertex>> . Similar utilizado puede ser el HashMultimap en Guava.

Este enfoque es genial, porque tienes O (1) (amortización) búsqueda de vértices y me devuelve una lista de todos los vértices adyacentes a este vértice 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 usa para representar gráficos dispersos, si está solicitando en Google, debe saber que el diagrama web es escaso. Puede manejarlos de una manera más escalable utilizando una BigTable .

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