LISTAS Y MATRICES

Lista de adyacencia

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sóllo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta. 

Matriz de adyacencia

Se trata de una matriz cuadrada de n filas *n columnas (siendo n el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento a ij vale {{1}} cuando haya una arista que una los vértices i y j En caso contrario el elemento a ij vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Una lista de adyacencia invertida almacena para cada vértice la lista de adjuntos
desde otros vértices.

Con la estructura de puede calcular el grado de entrada de cualquier vértice
solamente contando el numero de nodos de la lista del vértice requerido.