Lista de adyacencia

En teoría de grafos, una lista de adyacencia es una representación de todas las aristas o arcos de un grafo mediante una lista.

Si el grafo es no dirigido, cada entrada es un conjunto o multiconjunto de dos vértices conteniendo los dos extremos de la arista correspondiente. Si el grafo es dirigido, cada entrada es una tupla de dos nodos, uno denotando el nodo fuente y el otro denotando el nodo destino del arco correspondiente.

Típicamente, las listas de adyacentes son no ordenadas.

Referencias

• Joe Celko (2004). Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann. excerpt from Chapter 2: "Adjacency List Model". ISBN 1-55860-920-2. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. pp. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7. 
• David Eppstein (1996). ICS 161 Lecture Notes: Graph Algorithms. http://www.ics.uci.edu/~eppstein/161/960201.html. 
• Michael T. Goodrich and Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1. 
• Guido van Rossum (1998). Python Patterns — Implementing Graphs. http://www.python.org/doc/essays/graphs/. 

Enlaces externos

• Las Bibliotecas Boost implementan una lista de adyacencia eficiente.