5.2 Representación de los grafos.

 Los grafos se pueden representar de diferentes maneras, como por ejemplo:

• Representación por incidencia.

• Lista de incidencia: El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista.
• Matriz de incidencia: El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

• Representación por adyacencia.

• Listas de adyacencia: El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.
• Matriz de adyacencia: Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V2)).