c++ - tda - representacion de grafos
¿Qué es mejor, listas de adyacencia o matrices de adyacencia para problemas de gráficos en C++? (11)
¿Qué es mejor, listas de adyacencia o matriz de adyacencia, para problemas de gráficos en C ++? ¿Cuales son las ventajas y desventajas de cada uno?
De acuerdo, he compilado las complejidades de tiempo y espacio de las operaciones básicas en gráficos.
La imagen a continuación debe ser autoexplicativa.
Observe cómo es preferible la Matriz de adyacencia cuando esperamos que el gráfico sea denso, y cómo es preferible la Lista de adyacencia cuando esperamos que el gráfico sea escaso.
He hecho algunas suposiciones. Pregúntame si una complejidad (Tiempo o Espacio) necesita aclaración. (Por ejemplo, para un gráfico disperso, he tomado En para ser una pequeña constante, ya que he supuesto que la adición de un nuevo vértice agregará solo algunos bordes, porque esperamos que el gráfico permanezca escaso incluso después de agregarlo vértice.)
Por favor, dime si hay algún error.
Depende de lo que estés buscando.
Con las matrices de adyacencia puede responder rápidamente a preguntas sobre si un borde específico entre dos vértices pertenece al gráfico, y también puede tener inserciones y eliminaciones rápidas de bordes. La desventaja es que debe usar un espacio excesivo, especialmente para gráficos con muchos vértices, lo cual es muy ineficiente, especialmente si su gráfica es escasa.
Por otro lado, con las listas de adyacencia es más difícil verificar si un borde dado se encuentra en un gráfico, porque debe buscar a través de la lista correspondiente para encontrar el borde, pero son más eficientes en el uso del espacio.
Sin embargo, en general, las listas de adyacencia son la estructura de datos correcta para la mayoría de las aplicaciones de gráficos.
Depende del problema
Una matriz de adyacencia usa memoria O (n * n). Tiene búsquedas rápidas para verificar la presencia o ausencia de un borde específico, pero lento para iterar en todos los bordes.
Las listas de adyacencia utilizan la memoria en proporción a los bordes numéricos, lo que puede ahorrar mucha memoria si la matriz de adyacencia es escasa. Es rápido para iterar sobre todos los bordes, pero encontrar la presencia o ausencia del borde específico es ligeramente más lento que con la matriz.
Dependiendo de la implementación de la Matriz de Adyacencia, la ''n'' del gráfico debe conocerse antes para una implementación eficiente. Si el gráfico es demasiado dinámico y requiere expansión de la matriz de vez en cuando, ¿eso también se puede contar como un inconveniente?
Esta respuesta no es solo para C ++, ya que todo lo que se menciona es sobre las estructuras de datos, independientemente del idioma. Y, mi respuesta es asumir que usted conoce la estructura básica de las listas y matrices de adyacencia.
Memoria
Si la memoria es su principal preocupación, puede seguir esta fórmula para un gráfico simple que permite bucles:
Una matriz de adyacencia ocupa n 2/8 de espacio de bytes (un bit por entrada).
Una lista de adyacencia ocupa 8e espacio, donde e es el número de bordes (computadora de 32 bits).
Si definimos la densidad del gráfico como d = e / n 2 (número de aristas dividido por el número máximo de aristas), podemos encontrar el "punto de corte" donde una lista ocupa más memoria que una matriz:
8e> n 2/8 cuando d> 1/64
Entonces, con estos números (aún de 32 bits específicos), el punto de ruptura aterriza en 1/64 . Si la densidad (e / n 2 ) es mayor que 1/64, entonces es preferible una matriz si desea guardar memoria.
Puede leer sobre esto en wikipedia (artículo sobre matrices de adyacencia) y en muchos otros sitios.
Nota al margen : se puede mejorar la eficiencia del espacio de la matriz de adyacencia usando una tabla hash donde las claves son pares de vértices (solo no dirigidas).
Iteración y búsqueda
Las listas de adyacencia son una forma compacta de representar únicamente los bordes existentes. Sin embargo, esto tiene el costo de una posible búsqueda lenta de bordes específicos. Como cada lista es tan larga como el grado de un vértice, el peor momento de búsqueda de un borde específico puede convertirse en O (n), si la lista no está ordenada. Sin embargo, buscar los vecinos de un vértice se vuelve trivial, y para un gráfico escaso o pequeño, el costo de iterar a través de las listas de adyacencia puede ser insignificante.
Las matrices de adyacencia, por otro lado, usan más espacio para proporcionar un tiempo de búsqueda constante. Como cada entrada posible existe, puede verificar la existencia de una ventaja en tiempo constante utilizando índices. Sin embargo, la búsqueda de vecinos toma O (n) ya que necesita verificar todos los vecinos posibles. El inconveniente de espacio obvio es que para gráficos dispersos se agrega mucho relleno. Consulte la discusión de la memoria anterior para obtener más información sobre esto.
Si todavía no está seguro de qué usar, la mayoría de los problemas del mundo real producen gráficos dispersos y / o grandes, que son más adecuados para las representaciones de listas de adyacencia. Puede parecer más difícil de implementar, pero te aseguro que no, y cuando escribes un BFS o DFS y quieres buscar a todos los vecinos de un nodo, están a solo una línea de código. Sin embargo, tenga en cuenta que no estoy promocionando listas de adyacencia en general.
Esto se responde mejor con ejemplos.
Piensa en Floyd-Warshall por ejemplo. Tenemos que usar una matriz de adyacencia, o el algoritmo será más lento de manera asintótica.
¿O qué pasa si se trata de un gráfico denso en 30,000 vértices? Entonces, una matriz de adyacencia puede tener sentido, ya que almacenará 1 bit por par de vértices, en lugar de los 16 bits por borde (el mínimo que necesitaría para una lista de adyacencia): eso es 107 MB, en lugar de 1,7 GB.
Pero para algoritmos como DFS, BFS (y aquellos que lo usan, como Edmonds-Karp), Prioridad-primera búsqueda (Dijkstra, Prim, A *), etc., una lista de adyacencia es tan buena como una matriz. Bueno, una matriz puede tener una ligera ventaja cuando el gráfico es denso, pero solo por un factor constante no notable. (¿Cuánto? Es una cuestión de experimentar).
Para agregar a la respuesta de keyser5053 sobre el uso de la memoria.
Para cualquier gráfico dirigido, una matriz de adyacencia (a 1 bit por borde) consume n^2 * (1) bits de memoria.
Para un gráfico completo , una lista de adyacencia (con punteros de 64 bits) consume n * (n * 64) bits de memoria, sin incluir la sobrecarga de la lista.
Para un gráfico incompleto, una lista de adyacencia consume 0 bits de memoria, sin incluir la sobrecarga de la lista.
Para una lista de adyacencia, puede usar la fórmula siguiente para determinar el número máximo de aristas ( e ) antes de que una matriz de adyacencia sea óptima para la memoria.
edges = n^2 / s para determinar el número máximo de bordes, donde s es el tamaño del puntero de la plataforma.
Si su gráfico se actualiza dinámicamente, puede mantener esta eficiencia con un recuento de bordes promedio (por nodo) de n / s .
Algunos ejemplos (con punteros de 64 bits).
Para un gráfico dirigido, donde n es 300, el número óptimo de bordes por nodo que usa una lista de adyacencia es:
= 300 / 64
= 4
Si conectamos esto a la fórmula de keyser5053, d = e / n^2 (donde e es el recuento total del borde), podemos ver que estamos por debajo del punto de ruptura ( 1 / s ):
d = (4 * 300) / (300 * 300)
d < 1/64
aka 0.0133 < 0.0156
Sin embargo, 64 bits para un puntero pueden ser excesivos. Si, en cambio, utiliza enteros de 16 bits como desplazamientos del puntero, podemos ajustar hasta 18 bordes antes del punto de ruptura.
= 300 / 16
= 18
d = ((18 * 300) / (300^2))
d < 1/16
aka 0.06 < 0.0625
Cada uno de estos ejemplos ignora la sobrecarga de las propias listas de adyacencia ( 64*2 para un vector y punteros de 64 bits).
Si está buscando análisis de gráficos en C ++, probablemente el primer lugar para comenzar sería la biblioteca de gráficos de impulso , que implementa una serie de algoritmos, incluido BFS.
EDITAR
Esta pregunta previa sobre SO probablemente ayudará:
how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-searc h
Si usa una tabla hash en lugar de una matriz o lista de adyacencia, obtendrá mejor o el mismo tiempo de ejecución y espacio para todas las operaciones (la comprobación de un borde es O(1) , obteniendo todos los bordes adyacentes es O(degree) , etc.).
Sin embargo, hay una sobrecarga de factores constantes tanto para el tiempo de ejecución como para el espacio (la tabla hash no es tan rápida como la lista enlazada o la búsqueda de arreglos, y toma una cantidad decente de espacio adicional para reducir las colisiones).
Solo vamos a tratar de superar la compensación de la representación de la lista de adyacencia habitual, ya que otras respuestas han cubierto otros aspectos.
Es posible representar un gráfico en la lista de adyacencia con la consulta EdgeExists en tiempo constante amortizado aprovechando las estructuras de datos de Dictionary y HashSet . La idea es mantener vértices en un diccionario y para cada vértice mantenemos un conjunto de hash haciendo referencia a otros vértices con los que tiene bordes.
Una desventaja menor en esta implementación es que tendrá complejidad de espacio O (V + 2E) en lugar de O (V + E) como en la lista de adyacencia regular ya que los bordes se representan dos veces aquí (porque cada vértice tiene su propio conjunto de hash de bordes). Pero operaciones como AddVertex , AddEdge , RemoveEdge se pueden realizar en tiempo amortizado O (1) con esta implementación, excepto RemoveVertex que toma O (V) como matriz de adyacencia. Esto significaría que, aparte de la simplicidad de la implementación, la matriz de adyacencia no tiene ninguna ventaja específica. Podemos ahorrar espacio en un gráfico disperso con casi el mismo rendimiento en esta implementación de listas de adyacencia.
Eche un vistazo a las implementaciones a continuación en el repositorio de Github C # para más detalles. Tenga en cuenta que, para el gráfico ponderado, utiliza un diccionario anidado en lugar de una combinación de conjunto diccionario-hash para acomodar el valor del peso. De manera similar, para el gráfico dirigido hay conjuntos de hash separados para los bordes de entrada y salida.
Nota: Creo que al usar la eliminación diferida podemos optimizar aún más el funcionamiento de RemoveVertex en O (1) amortizado aunque no haya probado esa idea. Por ejemplo, al eliminar, simplemente marque el vértice como eliminado en el diccionario, y luego borre lentamente los bordes huérfanos durante otras operaciones.
Supongamos que tenemos un gráfico que tiene n número de nodos y m número de bordes,
Matriz de adyacencia: estamos creando una matriz que tiene n número de filas y columnas, por lo que en la memoria tomará un espacio que es proporcional a n 2 . Verificando si dos nodos nombrados como uyv tienen una ventaja entre ellos tomará Θ (1) vez. Por ejemplo, verificar (1, 2) es que un borde se verá como se muestra a continuación en el código:
if(matrix[1][2] == 1)
Si desea identificar todos los bordes, debe iterar sobre la matriz en este requerirá dos bucles anidados y tomará Θ (n 2 ). (Puede usar la parte triangular superior de la matriz para determinar todos los bordes, pero volverá a ser Θ (n 2 ))
Lista de adyacencia: estamos creando una lista en la que cada nodo también apunta a otra lista. Su lista tendrá n elementos y cada elemento apuntará a una lista que tenga un número de elementos que sea igual al número de vecinos de este nodo (observe la imagen para una mejor visualización). Por lo tanto, ocupará espacio en la memoria que es proporcional a n + m . Verificar si (u, v) es un borde tomará O (deg (u)) tiempo en el que deg (u) es igual al número de vecinos de u. Porque a lo sumo, debe iterar sobre la lista que señala el u. La identificación de todos los bordes tomará Θ (n + m).
Lista de adyacencia del gráfico de ejemplo
Debe hacer su elección de acuerdo a sus necesidades. Debido a mi reputación no pude poner la imagen de la matriz, lo siento por eso
