7.5. Una lista de adyacencia

Una forma más eficiente, respecto al uso del espacio, de implementar un grafo conectado de forma rala es usar una lista de adyacencia. En una implementación de lista de adyacencia mantenemos una lista maestra de todos los vértices en el objeto Grafo y además cada objeto Vértice en el grafo mantiene una lista de los otros vértices a los que está conectado. En nuestra implementación de la clase Vertice usaremos un diccionario en lugar de una lista donde las claves del diccionario son los vértices, y los valores son las ponderaciones. La Figura 4 ilustra la representación mediante una lista de adyacencia para el grafo de la Figura 2.

Figura 4: Representación mediante una lista de adyacencia de un grafo

Figura 4: Representación mediante una lista de adyacencia de un grafo

La ventaja de la implementación mediante una lista de adyacencia es que nos permite representar de forma compacta un grafo ralo. La lista de adyacencia también nos permite encontrar fácilmente todos los enlaces que están directamente conectados a un vértice particular.

You have attempted of activities on this page