Lista de adyacencia

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de noviembre de 2020; las comprobaciones requieren 2 ediciones .

Una lista de adyacencia es una forma de representar un gráfico como una colección de listas de vértices. Cada vértice del gráfico corresponde a una lista que consta de "vecinos" de este vértice.

Funciones de implementación

El gráfico en la imagen de arriba tiene la siguiente lista de adyacencia:
a	adyacente a	antes de Cristo
b	adyacente a	una c
C	adyacente a	un, b

Hay varias variaciones de la representación de lista de adyacencia de un grafo, que difieren en las características de asociación de vértices y colecciones de vecinos, la implementación de colecciones, si los bordes y vértices se incluyen en colecciones de vecinos o solo vértices, formas de representar bordes y vértices.

La implementación propuesta por Guido van Rossum utiliza una tabla hash para asociar cada vértice con una lista de vértices adyacentes. No hay representación explícita de bordes en esta estructura [1] [2] .
Kormen y otros han propuesto una implementación en la que los vértices están representados por un índice numérico en una matriz, en la que cada celda de la matriz se refiere a una lista unidireccional de vértices vecinos. [3]
Lista de adyacencia orientada a objetos propuesta por Goodrichy Tamassia, contiene clases especiales de vértices y aristas. Cada objeto de vértice contiene una referencia a una colección de aristas. Cada objeto de borde contiene referencias a vértices salientes y entrantes. [cuatro]

Comparación con la matriz de adyacencia

Comparación con matriz de adyacencia
Operación	lista de adyacencia	Matriz de adyacencia
Comprobación de un borde (x, y)	${\ estilo de visualización O (\| V \|)}$	$O(1)$
Determinar el grado de un vértice	$O(1)$	${\ estilo de visualización O (\| V \|)}$
Uso de memoria para gráficos dispersos	$O(\|V\|+\|E\|)$	${\ estilo de visualización O (\| V \| ^ {2})}$
Insertar/eliminar una cara	$O(1)$	${\ estilo de visualización O (d)}$
Recorrido gráfico	$O(\|V\|+\|E\|)$	${\ estilo de visualización O (\| V \| ^ {2})}$

Enlaces

↑ Guido van Rossum . Patrones de Python: implementación de gráficos (1998). Consultado el 4 de julio de 2016. Archivado desde el original el 25 de junio de 2016. (indefinido)
↑ Multimapa en guayaba . Consultado el 4 de julio de 2016. Archivado desde el original el 1 de febrero de 2019. (indefinido)
↑ Thomas H.Cormen ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein . Introducción a los Algoritmos , Segunda Edición . - MIT Press y McGraw-Hill, 2001. - Pág. 527-529 del apartado 22.1: Representaciones de grafos. — ISBN 0-262-03293-7 .
↑ Michael T. Goodrich y Roberto Tamassia. Diseño de algoritmos : fundamentos, análisis y ejemplos de Internet . - John Wiley & Sons , 2002. - ISBN 0-471-38365-1 .
↑ Steven SkienaManual de diseño de algoritmos (2ª ed.) (indefinido) . - 2010. - Pág. 152 del apartado 5.2: Estructuras de datos para grafos. — ISBN 0-387-00163-8 .