4.2. Representación de grafos.
Representación mediante listas de adyacencia.
- Para cada nodo de V tendremos una lista de aristas que parten de ese nodo. Estas listas están guardadas en un array de nodos cabecera.
- Grafo etiquetado: añadir un nuevo campo a los elementos de la lista.
- Si el grafo es no dirigido entonces cada arista (v, w) será representada dos veces, en la lista de v y en la de w.
- En grafos dirigidos.
- Calcular el grado de salida: recorrer la lista correspondiente. Grado de entrada: recorrer todas las listas.
- Otra posibilidad: tener otra lista con las aristas que llegan a un nodo dado.
- La mejor representación dependerá de las características del problema.