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à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 darestes, 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:, Secció 13.1.2: Operations on graphs 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, Exercise 22.1-7 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 Afegir vèrtex Afegir aresta Eliminar vèrtex Eliminar aresta Consulta: els vèrtexs x i y són adjacents? (suposant que es coneixen les seves posicions d'emmagatzematge) 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., Section 22.1: Representations of graphs, Section 13.1: Graph terminology and representations

Referències

Bibliografia

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 Tutorial sobre grafs (per Jebril FILALI)

Categoria:Teoria de grafs Categoria:Estructura de dades Categoria:Tipus abstracte de dades