Cerca en amplada

De Viquipèdia
Dreceres ràpides: navegació, cerca

La cerca en amplada (de l'anglès BFS - Breadth First Search) és un algorisme informàtic per recórrer o buscar elements en un graf (usat sovint en arbres). Intuïtivament, es comença a l'arrel (escollint algun node com a element arrel en el cas d'un graf) i s'exploren tots els veïns d'aquest node. A continuació per a cada un dels veïns s'exploren els seus respectius veïns adjacents, i així fins que es recorri tot l'arbre.

Formalment, BFS és un algorisme de cerca sense informació , que expandeix i examina tots els nodes d'un arbre sistemàticament per buscar una solució. L'algorisme no fa servir cap estratègia heurística.

Si les arestes tenen pesos negatius s'aplica l'algorisme de Bellman-Ford en alguna de les dues versions.

Procediment[modifica | modifica el codi]

Donat un vèrtex font, Breadth-first search sistemàticament explora els vèrtexs de G per "descobrir" tots els vèrtexs assolibles des s.

Calcula la distància (menor nombre de vèrtexs) desde s a tots els vèrtexs assolibles.

Després produeix un arbre BF amb arrel en s i que contindrà tots els vèrtexs assolibles.

El camí desde s a cada vèrtex en aquest recorregut conté el mínim nombre de vèrtexs. És el camí més curt mesurat en nombre de vèrtexs.

El seu nom es deu al fet que expandeix uniformement la frontera entre el descobert i el no descobert. Arriba als nodes de distància k, només després d'haver arribat a tots els nodes a distància k-1.

Pseudocodi[modifica | modifica el codi]

La nomenclatura addicional utilitzada és: Q = Cua de dades

1  procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t ← Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
12             u ← G.adjacentVertex(t,e)
13             if u is not marked:
14                  mark u
15                  enqueue u onto Q


* Manca recórrer vertexs no adjacents directament o indirectament al vertex origen "s",
doncs la cua queda buida sense els adjacents restants.

El temps d'execució és O (|V|+|E|). Noteu que cada node és posat a la cua un cop i la seva llista d'adjacència és recorreguda una vegada també.

Bibliografia[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Cerca en amplada Modifica l'enllaç a Wikidata