Grafos
Un grafo es una estructura compuesta por vértices y aristas que son las líneas que unen los vértices. Se representa con dos conjuntos:
- V = Vertices
- E = Aristas
Por ejemplo para representar que hay vuelos Madrid - Barcelona y Barcelona - Madrid
V = {Madrid, Barcelona} E = {(Madrid, Barcelona), (Barcelona, Madrid)}
Dirigido/no dirigido
Un grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un sentido definido, esto es, son relaciones asimétricas, a diferencia del grafo no dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido.
Con o sin coste
En los grafos con coste las aristas tienen asociado un valor númerico que expresa un coste, como distancia, esfuerzo o tiempo. Entre dos estaciones de metro sería por ejemplo el tiempo. Este coste puede ser distinto por sentido.
Ejemplo: representamos un grafo con dos vértices, el aeropuerto de Madrid y el de Barcelona. Y queremos indicar que de Madrid a Barcelona se tarda 60 minutos y de Barcelona a Madrid 65.
V = {Madrid, Barcelona}
E = {(Madrid, Barcelona, 60), (Barcelona, Madrid, 65)}
Densidad
En teoría de grafos, la densidad de un grafo es una propiedad que determina la proporción de aristas que posee. Un grafo denso es un grafo en el que el número de aristas es cercano al número máximo de aristas posibles, es decir, a las que tendría si el grafo fuera completo. Al contrario, un grafo disperso es un grafo con un número de aristas muy bajo, es decir, cercano al que tendría si fuera un grafo vacío.
La distinción entre grafos dispersos y densos es relativamente vaga. De acuerdo con Preiss,1 dado un grafo G = ( V , E ) 
Representado como listas de adyancencia o matriz de adyancencia
En las listas de adyacencia se representa cada vertices como primer elemento de la lista seguido de todos los vértices con los que está conectado de manera directa.
En las matrices de adyacenciaz se representan los vértices en una matriz con valor booleano que indica si hay conexión entre ambos.
Relación de densidad y tipo de representación.
| Densidad | Representación eficiente |
|---|---|
| Baja | Lista de adyacencia con listas enlazadas |
| Alta | Matriz de adyacencia |
Listas de adyacencia son más eficientes para matrices dispersas en grafos, ya que evitan asignar espacio para conexiones inexistentes, ahorran memoria, permiten acceso eficiente y son flexibles en la cantidad de nodos. La matriz de adyacencia desperdicia memoria al asignar espacio para todas las conexiones posibles, incluso si son cero, y puede ser menos eficiente en acceso y flexibilidad.
En grafos densos, donde la mayoría de los nodos están conectados, la matriz de adyacencia es más eficiente. La matriz aprovecha la estructura densa almacenando directamente todas las conexiones, lo que facilita el acceso rápido y ocupa menos espacio en comparación con las listas de adyacencia, que requieren almacenar enlaces a nodos vecinos y pueden llevar a un mayor uso de memoria y tiempo de acceso en grafos densos.
Operaciones de un grafo
Los grafos tienes estas operaciones: - insertarVertice() - insertarArista() - obtenerAdyacentes()