Graf (estructura de dades)
From Wikipedia, the free encyclopedia
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.).