# Graf (estructura de dades)

En ciències de la computació, un graf és un tipus abstracte de dades que implementa els conceptes matemàtics de graf no dirigit i graf dirigit.
Una estructura de dades de graf consisteix d'un conjunt finit (i possiblement alterable) de vèrtexs o nodes o punts, juntament amb un conjunt de parells no ordenats d'aquests vèrtexs, en el cas d'un graf no dirigit, o un conjunt de parells ordenats de vèrtexs, en el cas d'un graf dirigit. Aquests parells reben el nom d'arestes, arcs o línies en el cas d'un graf no dirigit, o fletxes, arestes dirigides, arcs dirigits o línies dirigides en el cas d'un graf dirigit. Els vèrtexs poden formar part del graf, o poden ser entitats externes representades per índexs enters o referències.
Una estructura de dades de graf també pot assignar a cada aresta un valor, com per exemple una etiqueta simbòlica o un atribut numèric (cost, capacitat, longitud, etc.).

## Operacions

Les operacions bàsiques sobre una estructura de dades de graf G inclouen:
* adjacent(G, x, y): comprova si existeix una aresta des del vèrtex x cap al vèrtex y.
* veïns(G, x): llista tots els vèrtexs y tals que existeix una aresta des del vèrtex x cap al vèrtex y.
* afegeix_vèrtex(G, x): afegeix el vèrtex x, si encara no existeix.
* elimina_vèrtex(G, x): elimina el vèrtex x, si existeix.
* afegeix_aresta(G, x, y): afegeix l'aresta des del vèrtex x cap al vèrtex y, si encara no existeix.
* elimina_aresta(G, x, y): elimina l'aresta des del vèrtex x cap al vèrtex y, si existeix.
* obté_valor_vèrtex(G, x): recupera el valor associat al vèrtex x.
* estableix_valor_vèrtex(G, x, v): modifica el valor associat al vèrtex x per tal que sigui v.
Les estructures que associen valors a les arestes també acostumen a incloure les següents operacions:
* obté_valor_aresta(G, x, y): recupera el valor associat amb l'aresta (x, y).
* estableix_valor_aresta(G, x, y, v): modifica el valor associat a l'aresta (x, y) per tal que sigui v.

## Representacions

A la pràctica, es poden utilitzar diferents estructures de dades per a la representació de grafs:

### Llista d'adjacència

    Els vèrtexs s'emmagatzemen com a registres o objectes, i cada vèrtex emmagatzema una llista de vèrtexs adjacents. Aquesta estructura de dades permet l'emmagatzematge als vèrtexs d'informació addicional. Encara s'hi pot dipositar més informació, si les arestes també s'emmagatzemen com a objectes; en tal cas, cada vèrtex té la informació de quines arestes hi són incidents, i cada aresta té la informació de quins vèrtexs hi són incidents.

### Matriu d'adjacència

    Matriu bidimensional, en la qual les files representen els vèrtexs origen i les columnes representen els vèrtexs destí. Cal emmagatzemar en una altra estructura la informació dels vèrtexs i de les arestes. Entre cada parell de vèrtexs només es pot emmagatzemar el cost d'una aresta.

### Matriu d'incidència

    Una matriu bidimensional amb entrades booleanes, on les files representen els vèrtexs i les columnes representen les arestes. Les entrades indiquen si el vèrtex de la fila és incident a l'aresta de la columna.
La següent taula proporciona informació sobre el cost en temps de diverses operacions sobre grafs, on |V| és el nombre de vèrtexs i |E| és el nombre d'arestes. En les representacions matricials, les entrades contenen el cost de resseguir una aresta. S'assumeix que el cost per a les arestes que no estan presents és ∞.
| | Llista d'adjacència | Matriu d'adjacència | Matriu d'incidència |
| Emmagatzemar graf | $O(|V|+|E|)$ | $O(|V|^{2})$ | $O(|V|\cdot |E|)$ |
| Afegir vèrtex | $O(1)$ | $O(|V|^{2})$ | $O(|V|\cdot |E|)$ |
| Afegir aresta | $O(1)$ | $O(1)$ | $O(|V|\cdot |E|)$ |
| Eliminar vèrtex | $O(|E|)$ | $O(|V|^{2})$ | $O(|V|\cdot |E|)$ |
| Eliminar aresta | $O(|E|)$ | $O(1)$ | $O(|V|\cdot |E|)$ |
| Consulta: els vèrtexs x i y són adjacents? (suposant que es coneixen les seves posicions d'emmagatzematge) | $O(|V|)$ | $O(1)$ | $O(|E|)$ |
| Observacions | Lent per eliminar vèrtexs i arestes, perquè necessita trobar tots els vèrtexs o arestes | Lent per afegir o eliminar vèrtexs, perquè cal redimensionar/copiar la matriu | Lent per afegir o eliminar vèrtexs i arestes, perquè cal redimensionar/copiar la matriu |
Les llistes d'adjacència representen de forma eficient els grafs dispersos. Si el graf és dens, és més eficient utilitzar una matriu d'adjacència, és a dir, quan el nombre d'arestes |E| és proper al quadrat del nombre de vèrtexs, |V|²; també s'utilitzen matrius d'adjacència si es necessita verificar ràpidament si existeix una aresta que connecta dos vèrtexs.

## Referències

* 1 2 Goodrich & Tamassia 2015, p. 360, Secció 13.1.2: Operations on graphs
* 1 2 Mehlhorn, K.; Näher, S. «Chapter 6: Graphs and their data structures». A: LEDA: A platform for combinatorial and geometric computing. Cambridge University Press, 1999, p. 240–282.
* ↑ Cormen et al., 2001, p. 528–529.
* ↑ Goodrich i Tamassia, 2015, p. 361-362.
* ↑ Cormen et al., 2001, p. 529–530.
* ↑ Goodrich i Tamassia, 2015, p. 363.
* ↑ Cormen et al. 2001, p. 531, Exercise 22.1-7
* ↑ Cormen et al. 2001, p. 527–531, Section 22.1: Representations of graphs
* ↑ Goodrich & Tamassia 2015, pàg. 355–364, Section 13.1: Graph terminology and representations

## Bibliografia

* Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. 2a edició. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
* Goodrich, Michael T.; Tamassia, Roberto. Algorithm Design and Applications. Wiley, 2015.

## Vegeu també

* Recorregut de grafs per a diferents estratègies per a recórrer un graf
* Base de dades orientada a grafs per a persistència de grafs
* Reescriptura de grafs per a transformacions de grafa basades en regles

## Enllaços externs

* Boost Graph Library: llibreria de grafs en C++
* Networkx: llibreria de grafs en Python Arxivat 2013-03-10 a Wayback Machine.
* Tutorial sobre grafs (per Jebril FILALI) Arxivat 2015-04-19 a Wayback Machine.
Viccionari