Graf (estructura de dades)

Un graf amb tres vèrtexs i tres arestes

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.

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