Grafo (tipo de senya abstracta)


Un grafo en l'àmbit de les ciències de la computació és un tipo abstracte de senyes (TAD), que consistix en un conjunt de nodos (també cridats vèrtiços) i un conjunt d'arcs (arestes) que establixen relacions entre els nodos. El concepte de grafo TAD descendix directament del concepte matemàtic de grafo.
Formalment, un grafo es definix com , sent V un conjunt els elements del qual són els vèrtiços del grafo i A un conjunt els elements del qual són les arestes, les quals són parells (ordenats si el grafo és dirigit) d'elements en V.
Formes de representació
Existixen diferents implementacions del tipo grafo: en una matriu de adyacencies (forma acotada) i en llistes i multilistas de adyacencia (no acotades).
- Matriu de adjacències: s'associa cada fila i cada columna a cada nodo del grafo, sent els elements de la matriu la relació entre els mateixos, prenent els valors d'1 si existix l'aresta i 0 en cas contrari.
- Llista de adjacències: s'associa a cada nodo del grafo una llista que continga tots aquells nodos que siguen adjacents a ell.
Especificació dels tipos abstractes de senyes d'un grafo no dirigit
Generadors
Crear un grafo buit: Torna un grafo buit.
- op crearGrafo : -> Grafo [ctor] .
Afegir una aresta: Donat un grafo, afig una relació entre dos nodos de dit grafo.
- op añadirArista : Grafo Nodo Nodo -> [Grafo] [ctor] .
Afegir un nodo: Donat un grafo, inclou un nodo en ell, en cas en el que no existixca prèviament.
- op añadirNodo : Grafo Nodo -> Grafo [ctor] .
Constructors
Borrar nodo: Torna un grafo sense un nodo i les arestes relacionades en ell. Si dit nodo no existix es torna el grafo inicial.
- op borrarNodo : Grafo Nodo -> Grafo .
Borrar aresta: Torna un grafo sense l'aresta indicada. En cas que l'aresta no existixca torna el grafo inicial.
- op borrarArista : Grafo Nodo Nodo -> Grafo .
Selectores
Grafo Buit: Comprova si un grafo no té cap nodo.
- op esVacio : Grafo -> Bool .
Contindre Nodo: Comprova si un nodo pertany a un grafo.
- op conté : Grafo Nodo -> Bool .
Adjacents: Comprova si dos nodos tenen una aresta que els relacione.
- op adjacents : Grafo Nodo Nodo -> Bool .
Per a l'especificació d'un grafo dirigit tenim que modificar algunes de les equacions de les operacions borrarArista i añadirArista per a que no es considere el cas d'arestes bidireccionals.
I substituir l'operació adjacents per:
- op predecessor : Grafo Nodo Nodo -> Bool .
- op successor : Grafo Nodo Nodo -> Bool .
- Este artícul conté una traducció derivada de «Grafo (tipo de dato abstracto)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

