Grafo (tipo de dato abstracto)
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 A un conjunto cuyos elementos son las aristas, las cuales son pares (ordenados si el grafo es dirigido) de elementos en V.
Formas de representación
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.
- Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.
Especificación de los tipos abstractos de datos de un grafo no dirigido
Generadores
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
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
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
- Librería de C++ para grafos
- Rutinas de grafos en Perl
- Software para alinear/comparar grafos
- Software de visualización de grafos