Summary
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
editarExisten 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
editarGeneradores
editarCrear 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
editarBorrar 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
editarGrafo 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- Visualizaciones interactivas
- Notas
- Librería de C++ para grafos
- Rutinas de grafos en Perl
- Estructuras y algoritmos de grafos para .NET
- Software para alinear/comparar grafos
- Software de visualización de grafos
Datos: Q2479726
Multimedia: Graph (abstract data type) / Q2479726
