Grafo (estructura de datos)

Un grafo de 6 vértices y 7 aristas.

Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto 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.

Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de 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 el 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 Vacio: 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

• Visualizaciones interactivas
• Notas
• Librería de C++ para grafos
• Rutinas de grafos en Perl
• Estructuras y algoritmos de grafos para .NET
• Software de visualización de grafos