¿Qué es mejor, listas de adyacencia o matrices de adyacencia para problemas de gráficos en C ++?

129

¿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?

magiix
fuente
21
La estructura que usa no depende del idioma sino del problema que está tratando de resolver.
avakar
1
Me refería a un uso general como el algoritmo djikstra, hice esta pregunta porque no sé si vale la pena probar la implementación de la lista vinculada porque es más difícil de codificar que la matriz de adyacencia.
magiix
Las listas en C ++ son tan fáciles como escribir std::list(o mejor aún std::vector).
avakar
1
@avakar: o std::dequeo std::set. Depende de la forma en que el gráfico cambiará con el tiempo y qué algoritmos tiene la intención de ejecutar en ellos.
Alexandre C.

Respuestas:

125

Depende del problema.

Matriz de adyacencia

  • Utiliza memoria O (n ^ 2)
  • Es rápido buscar y verificar la presencia o ausencia de un borde específico
    entre cualquiera de los dos nodos O (1)
  • Es lento iterar sobre todos los bordes
  • Es lento agregar / eliminar un nodo; una operación compleja O (n ^ 2)
  • Es rápido agregar un nuevo borde O (1)

Lista de adyacencia

  • El uso de la memoria depende del número de bordes (no del número de nodos), lo
    que podría ahorrar mucha memoria si la matriz de adyacencia es escasa
  • Encontrar la presencia o ausencia de un borde específico entre dos nodos
    es ligeramente más lento que con la matriz O (k); donde k es el número de nodos vecinos
  • Es rápido iterar sobre todos los bordes porque puede acceder a cualquier nodo vecino directamente
  • Es rápido agregar / eliminar un nodo; más fácil que la representación matricial
  • Es rápido agregar un nuevo borde O (1)
Mark Byers
fuente
las listas enlazadas son más difíciles de codificar, ¿cree que vale la pena dedicar un tiempo a la implementación para aprenderla?
magiix
11
@magiix: Sí, creo que debería entender cómo codificar listas vinculadas si es necesario, pero también es importante no reinventar la rueda: cplusplus.com/reference/stl/list
Mark Byers
¿Alguien puede proporcionar un enlace con un código limpio para decir Breadth primera búsqueda en formato de listas vinculadas?
magiix
78

Esta respuesta no es solo para C ++, ya que todo lo mencionado se refiere a las estructuras de datos en sí mismas, independientemente del lenguaje. Y, mi respuesta es asumir que conoces 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 permita bucles:

Una matriz de adyacencia ocupa n 2 /8 Superficie byte (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 ruptura" 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 específicos de 32 bits), el punto de ruptura cae en 1/64 . Si la densidad (e / n 2 ) es mayor que 1/64, entonces es preferible una matriz si desea ahorrar 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 espacial de la matriz de adyacencia mediante el uso de una tabla hash donde las claves son pares de vértices (solo no dirigidos).

Iteración y búsqueda

Las listas de adyacencia son una forma compacta de representar solo los bordes existentes. Sin embargo, esto tiene el costo de una posible búsqueda lenta de bordes específicos. Dado que cada lista es tan larga como el grado de un vértice, el peor tiempo de búsqueda de un borde específico puede convertirse en O (n), si la lista no está ordenada. Sin embargo, buscar a 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. Dado que existen todas las entradas posibles, puede verificar la existencia de un borde en tiempo constante utilizando índices. Sin embargo, la búsqueda de vecinos toma O (n) ya que debe verificar todos los vecinos posibles. El inconveniente obvio del espacio es que para gráficos dispersos se agrega mucho relleno. Consulte la discusión sobre la memoria anterior para obtener más información al respecto.

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 le aseguro que no lo son, y cuando escribe un BFS o DFS y desea 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.

Keyser
fuente
9
+1 para obtener información, pero esto tiene que ser corregido por la estructura de datos real utilizada para almacenar las listas de adyacencia. Es posible que desee almacenar para cada vértice su lista de adyacencia como un mapa o un vector, en cuyo caso los números reales en sus fórmulas deben actualizarse. Además, se pueden usar cálculos similares para evaluar los puntos de equilibrio para la complejidad temporal de algoritmos particulares.
Alexandre C.
3
Sí, esta fórmula es para un escenario específico. Si desea una respuesta aproximada, siga adelante y use esta fórmula, o modifíquela según sus especificaciones según sea necesario (por ejemplo, la mayoría de las personas tienen una computadora de 64 bits hoy en día :))
keyer
1
Para aquellos interesados, la fórmula para el punto de ruptura (número máximo de aristas promedio en un gráfico de n nodos) es e = n / sdónde sestá el tamaño del puntero.
deceleratedcaviar
33

Bien, he compilado las complejidades de tiempo y espacio de las operaciones básicas en gráficos.
La imagen a continuación debe explicarse por sí misma.
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únteme si una complejidad (Tiempo o Espacio) necesita aclaración. (Por ejemplo, para un gráfico disperso, he considerado que En es una constante pequeña, ya que supuse que la adición de un nuevo vértice agregará solo unos pocos bordes, porque esperamos que el gráfico permanezca disperso incluso después de agregar eso vértice.)

Por favor, dime si hay algún error.

ingrese la descripción de la imagen aquí

John Red
fuente
En caso de que no se sepa si el gráfico es denso o disperso, ¿sería correcto decir que la complejidad del espacio para una lista de adyacencia sería O (v + e)?
Para los algoritmos más prácticos, una de las operaciones más importantes es iterar a través de todos los bordes que salen de un vértice dado. Es posible que desee agregarlo a su lista: es O (grado) para AL y O (V) para AM.
máximo
@johnred, ¿no es mejor decir que Agregar un vértice (tiempo) para AL es O (1) porque en lugar de O (en) porque realmente no agregamos bordes al agregar un vértice. Agregar una arista puede tratarse como una operación separada. Para AM tiene sentido tener en cuenta, pero incluso allí solo necesitamos inicializar las filas y columnas relevantes del nuevo vértice a cero. La adición de bordes incluso para AM puede explicarse por separado.
Usman
¿Cómo se agrega un vértice a AL O (V)? Tenemos que crear una nueva matriz, copiar los valores anteriores en ella. Debería ser O (v ^ 2).
Alex_ban
19

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áfico es escaso.

Por otro lado, con las listas de adyacencia es más difícil verificar si un borde dado está en un gráfico, porque debe buscar en la lista apropiada para encontrar el borde, pero son más eficientes en cuanto al espacio.

Generalmente, sin embargo, las listas de adyacencia son la estructura de datos correcta para la mayoría de las aplicaciones de gráficos.

Alex Ntousias
fuente
¿Qué sucede si utiliza diccionarios para almacenar la lista de adyacencia, que le dará la presencia de una ventaja en O (1) tiempo amortizado.
Rohith Yeravothula
10

Supongamos que tenemos un gráfico que tiene n número de nodos ym número de aristas,

Gráfico de ejemplo
ingrese la descripción de la imagen aquí

Matriz de adyacencia: estamos creando una matriz que tiene n número de filas y columnas, por lo que en la memoria ocupará un espacio proporcional a n 2 . Comprobar si dos nodos nombrados como u y v tienen una ventaja entre ellos llevará Θ (1) tiempo. Por ejemplo, la comprobación de (1, 2) es un borde similar al siguiente en el código:

if(matrix[1][2] == 1)

Si desea identificar todos los bordes, debe iterar sobre la matriz, ya que esto requerirá dos bucles anidados y tomará Θ (n 2 ). (Puede usar la parte triangular superior de la matriz para determinar todos los bordes, pero será nuevamente Θ (n 2 ))

Lista de adyacencia: estamos creando una lista que cada nodo también apunta a otra lista. Su lista tendrá n elementos y cada elemento apuntará a una lista que tenga una cantidad de elementos que sea igual a la cantidad de vecinos de este nodo (busque una mejor visualización en la imagen). Por lo tanto, ocupará un espacio en la memoria que es proporcional a n + m . Comprobar si (u, v) es un borde llevará tiempo O (deg (u)) 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 la u. Identificar todos los bordes tomará Θ (n + m).

Lista de adyacencia del gráfico de ejemplo

ingrese la descripción de la imagen aquí
Debe hacer su elección según sus necesidades. Debido a mi reputación, no pude poner una imagen de matriz, lo siento.

Muhammed Kadir
fuente
7

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 anterior sobre SO probablemente ayudará:

cómo-crear-ac-boost-undirected-graph-and-traverse-it-in-depth-first-searc h

Nerd Binario
fuente
Gracias
revisaré
+1 para el gráfico de impulso. Este es el camino a seguir (excepto, por supuesto, si es con fines educativos)
Tristram Gräbener
5

Esto se responde mejor con ejemplos.

Piense en Floyd-Warshall por ejemplo. Tenemos que usar una matriz de adyacencia, o el algoritmo será asintóticamente más lento.

¿O qué pasa si es un gráfico denso en 30,000 vértices? Entonces, una matriz de adyacencia podría 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), búsqueda de prioridad primero (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 cuestión de experimentar).

Evgeni Sergeev
fuente
2
Para algoritmos como DFS y BFS, si usa una matriz, debe verificar toda la fila cada vez que desee encontrar nodos adyacentes, mientras que ya tiene nodos adyacentes en una lista adyacente. ¿Por qué piensas an adjacency list is as good as a matrixen esos casos?
realUser404
@ realUser404 Exactamente, escanear una fila de matriz completa es una operación O (n). Las listas de adyacencia son mejores para gráficos dispersos cuando necesita atravesar todos los bordes salientes, pueden hacerlo en O (d) (d: grado del nodo). Sin embargo, las matrices tienen un mejor rendimiento de caché que las listas de adyacencia, debido al acceso secuencial, por lo que para gráficos algo densos, escanear matrices puede tener más sentido.
Jochem Kuijpers el
3

Para agregar a las respuestas 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, excluyendo la sobrecarga de la lista.

Para un gráfico incompleto, una lista de adyacencia consume 0bits de memoria, excluyendo la sobrecarga de la lista.


Para una lista de adyacencia, puede usar la siguiente fórmula 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 / spara determinar el número máximo de bordes, donde sestá el tamaño del puntero de la plataforma.

Si su gráfico se está actualizando dinámicamente, puede mantener esta eficiencia con un conteo de bordes promedio (por nodo) de n / s.


Algunos ejemplos con punteros de 64 bits y gráfico dinámico (un gráfico dinámico actualiza la solución de un problema de manera eficiente después de los cambios, en lugar de volver a calcularlo desde cero cada vez que se realiza un cambio).

Para un gráfico dirigido, donde nes 300, el número óptimo de aristas 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 eestá el conteo total de bordes), 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 su lugar utiliza enteros de 16 bits como compensaciones de 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 listas de adyacencia ( 64*2para un vector y punteros de 64 bits).

caviar desacelerado
fuente
No entiendo la parte d = (4 * 300) / (300 * 300), ¿no debería ser así d = 4 / (300 * 300)? Ya que la fórmula es d = e / n^2.
Saurabh
2

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 la expansión de la matriz de vez en cuando, ¿eso también puede contarse como una desventaja?

ChrisOdney
fuente
1

Si usa una tabla hash en lugar de una matriz o lista de adyacencia, obtendrá un mejor o el mismo tiempo de ejecución y espacio de O grande para todas las operaciones (comprobar si hay un borde O(1), obtener todos los bordes adyacentes esO(degree) , etc.).

Sin embargo, hay una sobrecarga de factor constante tanto para el tiempo de ejecución como para el espacio (la tabla hash no es tan rápida como la lista vinculada o la búsqueda de matriz, y ocupa una cantidad decente de espacio extra para reducir las colisiones).

max
fuente
1

Solo voy a tratar de superar la compensación de la representación regular de la lista de adyacencia, 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 Dictionary y HashSet . La idea es mantener los vértices en un diccionario, y para cada vértice, mantenemos un conjunto de hash que hace referencia a otros vértices con los que tiene bordes.

Una compensación menor en esta implementación es que tendrá una 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 las operaciones como AddVertex , AddEdge , RemoveEdge se pueden realizar en tiempo amortizado O (1) con esta implementación, a excepción de RemoveVertex que toma O (V) como matriz de adyacencia. Esto significaría que, aparte de la simplicidad de 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 lista de adyacencia.

Eche un vistazo a las implementaciones a continuación en el repositorio de Github C # para obtener más detalles. Tenga en cuenta que para el gráfico ponderado utiliza un diccionario anidado en lugar de una combinación de conjunto de diccionario-hash para acomodar el valor de peso. Del mismo modo para el gráfico dirigido, hay conjuntos de hash separados para los bordes de entrada y salida.

Algoritmos Avanzados

Nota: Creo que con la eliminación diferida podemos optimizar aún más la operación RemoveVertex a O (1) amortizado, aunque no he probado esa idea. Por ejemplo, después de la eliminación, simplemente marque el vértice como eliminado en el diccionario y luego borre perezosamente los bordes huérfanos durante otras operaciones.

justcoding121
fuente
Para la matriz de adyacencia, eliminar el vértice toma O (V ^ 2) no O (V)
Saurabh
Si. Pero si usa un diccionario para rastrear los índices de la matriz, se reducirá a O (V). Eche un vistazo a esta implementación RemoveVertex .
justcoding121