Materia: #técnicas_y_diseños_de_algoritmos

Tags: Algoritmo, Arboles, Grafos, Dígrafos

BFS

Para recorrer un árbol uno de los algoritmos mas conocidos BFS (breadth-first search) consiste en, dado un nodo como punto de partida, recorrer a todos sus vecinos instantáneos antes de pasar al siguiente nivel. Es decir, vamos recorriendo el árbol de nivel en nivel.

Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución.

flowchart TD

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))
id7((7))
id8((8))
id9((9))
id10((10))
id11((11))
id12((12))

id1 --- id2
id1 --- id3
id1 --- id4
id2 --- id5
id2 --- id6
id4 --- id7
id4 --- id8
id5 --- id9
id5 --- id10
id7 --- id11
id7 --- id12

En este dibujo se puede ver el orden en el que son visitados los nodos si se corre el algoritmo desde la raíz.

Pseudocódigo

BFS(Grafo, raiz):
	porVisitar = {raiz};
	contador = 0;
	ordenDeBusqueda[contador] = {raiz}
	while (porVisitar no este vacia) do:
		actual = porVisitar.pop();
		if (existe un camino a un nodo N que no se encuentre en porVisitar) do:
			porVisitar = porVisitar.push(N);
			contador = contador + 1;
			ordenDeBusqueda[contador] = actual;
		else:
			porVisitar = porVisitar - {actual};
		end if;
	end while;
	return ordenDeBusqueda;

En este pseucódigo devolvemos la lista del orden en que fueron visitados los nodos, pero podríamos buscar otra información.

Complejidad

En términos de tiempo el algoritmo tiene una complejidad de $O(|V|+|E|)$, es decir, la suma entre la cantidad de vértices y aristas. El razonamiento es porque en el peor caso, cada vértice y cada arista será visitado por el algoritmo.

Por otro lado, en términos de memoria, y sin contar el espacio del propio grafo, necesitaríamos como mucho $O(|V|)$, ya que lo único que estamos guardando en el proceso es los nodos que no visitamos. En el peor caso, un nodo conecta con todos los demás, y la lista tiene todos los vértices.

Usos

El algoritmo de BFS es muy usado para calcular la distancia entre dos nodos dados, tanto en arboles, grafos o dígrafos.