Grafo (estructura de datos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Un grafo de 6 vértices y 7 aristas.

Un grafo en el ámbito de las ciencias de la computación es un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.

Formalmente, un grafo se define como , siendo V un conjunto cuyos elementos son los vértices del grafo y, E uno cuyos elementos son las aristas (edges en inglés), las cuales son pares (ordenados si el grafo es dirigido) de elementos en V.

Formas de representación[editar]

Existen diferentes implementaciones del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas).

  • Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.

Matriz de adyacencia.jpg

  • Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.

Listas de adyacencia.jpg

Especificación de los tipos abstractos de datos de un grafo no dirigido[editar]

Generadores[editar]

Crear un grafo vacío: Devuelve un grafo vacío.

  • op crearGrafo : -> Grafo [ctor] .

Añadir una arista: Dado un grafo, añade una relación entre dos nodos de dicho grafo.

  • op añadirArista : Grafo Nodo Nodo -> [Grafo] [ctor] .

Añadir un nodo: Dado un grafo, incluye un nodo en él, en caso en el que no exista previamente.

  • op añadirNodo : Grafo Nodo -> Grafo [ctor] .

Constructores[editar]

Borrar nodo: Devuelve un grafo sin un nodo y las aristas relacionadas con él. Si dicho nodo no existe se devuelve el grafo inicial.

  • op borrarNodo : Grafo Nodo -> Grafo .

Borrar arista: Devuelve un grafo sin la arista indicada. En caso de que la arista no exista devuelve el grafo inicial.

  • op borrarArista : Grafo Nodo Nodo -> Grafo .

Selectores[editar]

Grafo Vacío: Comprueba si un grafo no tiene ningún nodo.

  • op esVacio : Grafo -> Bool .

Contener Nodo: Comprueba si un nodo pertenece a un grafo.

  • op contiene : Grafo Nodo -> Bool .

Adyacentes: Comprueba si dos nodos tienen una arista que los relacione.

  • op adyacentes : Grafo Nodo Nodo -> Bool .

Para la especificación de un grafo dirigido tenemos que modificar algunas de las ecuaciones de las operaciones borrarArista y añadirArista para que no se considere el caso de aristas bidireccionales.

Y sustituir la operación adyacentes por:

  • op predecesor : Grafo Nodo Nodo -> Bool .
  • op sucesor : Grafo Nodo Nodo -> Bool .

Enlaces externos[editar]