Mostra la font per a Graf (estructura de dades)

[[Fitxer:Directed.svg|miniatura|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àtiques|matemàtics]] de [[Graf (matemàtiques)|graf no dirigit]] i [[graf dirigit]].

Una estructura de dades de graf consisteix d'un [[Conjunt (estructura de dades)|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ència (informàtica)|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:<ref name="gt-ops1">{{harvnb|Goodrich|Tamassia|2015|p=360}}, Secció 13.1.2: Operations on graphs</ref><ref name="gt-ops2">{{ref-llibre|capítol=Chapter 6: Graphs and their data structures|pàgines=240–282|títol=LEDA: A platform for combinatorial and geometric computing|nom=K.|cognom=Mehlhorn|enllaçautor=Kurt Mehlhorn|nom2=S.|cognom2=Näher|editorial=[[Cambridge University Press]]|any=1999}}</ref>
* <code>adjacent</code>(''G'', ''x'', ''y''): comprova si existeix una aresta des del vèrtex ''x'' cap al vèrtex ''y''.
* <code>veïns</code>(''G'', ''x''): llista tots els vèrtexs ''y'' tals que existeix una aresta des del vèrtex ''x'' cap al vèrtex ''y''.
* <code>afegeix_vèrtex</code>(''G'', ''x''): afegeix el vèrtex ''x'', si encara no existeix.
* <code>elimina_vèrtex</code>(''G'', ''x''): elimina el vèrtex ''x'', si existeix.
* <code>afegeix_aresta</code>(''G'', ''x'', ''y''): afegeix l'aresta des del vèrtex ''x'' cap al vèrtex ''y'', si encara no existeix.
* <code>elimina_aresta</code>(''G'', ''x'', ''y''): elimina l'aresta des del vèrtex ''x'' cap al vèrtex ''y'', si existeix.
* <code>obté_valor_vèrtex</code>(''G'', ''x''): recupera el valor associat al vèrtex ''x''.
* <code>estableix_valor_vèrtex</code>(''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:<ref name="gt-ops1"/><ref name="gt-ops2"/>
* <code>obté_valor_aresta</code>(''G'', ''x'', ''y''): recupera el valor associat amb l'aresta (''x'', ''y'').
* <code>estableix_valor_aresta</code>(''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]]{{sfn|Cormen|Leiserson|Rivest|Stein|2001|pp=528–529}}{{sfn|Goodrich|Tamassia|2015|pp=361-362}}
: Els vèrtexs s'emmagatzemen com a registres o objectes, i cada vèrtex emmagatzema una [[Llista (estructura de dades)|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]]{{sfn|Cormen|Leiserson|Rivest|Stein|2001|pp=529–530}}{{sfn|Goodrich|Tamassia|2015|p=363}}
: 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]]<ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=531}}, Exercise 22.1-7</ref>
: 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 [[Complexitat computacional|cost en temps]] de diverses operacions sobre grafs, on |''V''| és el nombre de vèrtexs i |''E''| és el nombre d'arestes.{{Citació necessària|data=2016}} 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 ∞.

{| class=wikitable
|-
!
! Llista d'adjacència
! Matriu d'adjacència
! Matriu d'incidència
|-
| Emmagatzemar graf
| <math>O(|V|+|E|)</math>
| <math>O(|V|^2)</math>
| <math>O(|V|\cdot|E|)</math>
|-
| Afegir vèrtex
| <math>O(1)</math>
| {{cel·la|parcial|<math>O(|V|^2)</math>}}
| {{cel·la|parcial|<math>O(|V|\cdot|E|)</math>}}
|-
| Afegir aresta
| <math>O(1)</math>
| <math>O(1)</math>
| {{cel·la|parcial|<math>O(|V|\cdot|E|)</math>}}
|-
| Eliminar vèrtex
| {{cel·la|parcial|<math>O(|E|)</math>}}
| {{cel·la|parcial|<math>O(|V|^2)</math>}}
| {{cel·la|parcial|<math>O(|V|\cdot|E|)</math>}}
|-
| Eliminar aresta
| {{cel·la|parcial|<math>O(|E|)</math>}}
| <math>O(1)</math>
| {{cel·la|parcial|<math>O(|V|\cdot|E|)</math>}}
|-
| Consulta: els vèrtexs ''x'' i ''y'' són adjacents? (suposant que es coneixen les seves posicions d'emmagatzematge)
| <math>O(|V|)</math>
| <math>O(1)</math>
| <math>O(|E|)</math>
|-
| 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 [[Graf dispers|grafs dispersos]]. Si el graf és [[Graf dens|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.<ref name="clrs">{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=527–531}}, Section 22.1: Representations of graphs</ref><ref name="gt">{{harvnb|Goodrich|Tamassia|2015|pp=355–364}}, Section 13.1: Graph terminology and representations</ref>

== Referències ==
{{referències}}

== Bibliografia ==
* {{ref-llibre |enllaçautor=Thomas H. Cormen |nom=Thomas H. |cognom=Cormen |enllaçautor2=Charles E. Leiserson |nom2=Charles E. |cognom2=Leiserson |enllaçautor3=Ronald L. Rivest |nom3=Ronald L. |cognom3=Rivest |enllaçautor4=Clifford Stein |nom4=Clifford |cognom4=Stein |any=2001 |títol=[[Introduction to Algorithms]] |edició=2a edició |editorial=MIT Press and McGraw-Hill |isbn=0-262-03293-7}}
* {{ref-llibre|títol=Algorithm Design and Applications|nom=Michael T.|cognom=Goodrich|enllaçautor=Michael T. Goodrich|nom2=Roberto|cognom2=Tamassia|enllaçautor2=Roberto Tamassia|editorial=Wiley|any=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 ==
* [http://www.boost.org/libs/graph Boost Graph Library: llibreria de grafs en C++]
* [http://networkx.github.com/ Networkx: llibreria de grafs en Python] {{Webarchive|url=https://web.archive.org/web/20130310032954/http://networkx.github.com/ |date=2013-03-10}}
* [http://www.roxtutorial.com/graphs-java/ Tutorial sobre grafs (per Jebril FILALI)] {{Webarchive|url=https://web.archive.org/web/20150419084122/http://www.roxtutorial.com/graphs-java |date=2015-04-19}}

{{Viccionari-lateral|Graf}}

{{ORDENA:Graf (Estructura De Dades)}}
[[Categoria:Teoria de grafs]]
[[Categoria:Estructura de dades]]
[[Categoria:Tipus abstracte de dades]]