Listas de adyacencia

1. ALMACENAMIENTO DE UN GRAFO EN UNA LISTA DE ADYACENCIA Y ADYACENCIA INVERTIDA

2. LISTA DE ADYACENCIA U na   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.

3. REPRESENTACIÓN (GRAFO DIRIGIDO-LISTA DE ADYACENCIA) GRAFO DIRIGIDO LISTA DE ADYACENCIA MATRIZ DE ADYACENCIA

4. REPRESENTACIÓN (GRAFO DIRIGIDO-LISTA DE ADYACENCIA INVERSA) 1 2 3 4 5 6

5. REPRESENTACIÓN (GRAFO NO DIRIGIDO-LISTA DE ADYACENCIA) GRAFO NO DIRIGIDO LISTA DE ADYACENCA MATRIZ DE ADYACENCIA

6. ALMACENAMIENTO EN UNA ESTRUCTURA DE DATOS ESTÁTICA ( arreglos o  arrays . ) VENTAJA: Acceso simultáneo a la información. Por ende la velocidad de búsqueda es prácticamente nula. ( Ventaja para el procesador CPU ). DESVENTAJA: Desperdicio de memoria. Por ejemplo, si sabemos que eventualmente tendremos 100 clientes y creamos un arreglo de 100 posiciones. Mientras se cumple el objetivo de tener 100 clientes teniendo por ejemplo solo 20 clientes, estaremos desperdiciando el espacio de 80 clientes; espacio que podríamos utilizar de manera más eficiente. ( Desventaja para la memoria RAM ).

7. ALMACENAMIENTO EN UNA ESTRUCTURA DE DATOS ESTÁTICA ( N odos o  Linkers ) VENTAJA:  Gracias a esto podemos aprovechar de manera muy eficiente la memoria RAM ya que solo utilizaremos lugares de memoria una vez los necesitamos, sin necesidad de desperdiciar espacio. ( Ventaja para la memoria RAM ). DESVENTAJA: Para acceder a los datos, debido a que el nivel de acceso principal siempre es la primera posición, y la primera posición no tiene referencia directa a todos los elementos de la estructura, se tiene que recorrer nodo por nodo hasta llegar a la posición buscada. Esto reduce en gran manera la velocidad de procesamiento en el momento de una búsqueda. ( Desventaja para el procesador CPU ).

8. GRACIAS…!!