TEORIA DE GRAFOS ALGORITMO DE BÚSQUEDA EN ANCHURA (BFS)

TEORIA DE GRAFOS

ALGORITMO DE BÚSQUEDA EN ANCHURA (BFS)

EMPEZAR

ALGORITMO DE BÚSQUEDA EN ANCHURA (BFS)

TEORIA DE GRAFOS

La búsqueda en anchura(BFS) supone que el recorrido se haga por niveles, para lo cual, se recorre los nodos de un grafo, comenzando en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo), para luego explorar todos los vecinos de este nodo. A continuación, para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el grafo

Algoritmos de Teoria de Grafos

TEORIA DE GRAFOS

ALGORITMO BFS

Se hace uso de la siguiente imagen de un grafo ejemplo, en donde cada color representa un nivel, tomando como raíz o nodo inicial el que tiene el número 1. El recorrido se hará en orden numérico de forma consecutiva hasta llegar al nodo número 7.

TEORIA DE GRAFOS

ALGORITMO BFS

La estrategia es un TDA cola (FIFO) que permita almacenar temporalmente todos los nodos de un nivel, para ser procesados antes de pasar al siguiente nivel hasta que la cola esté vacía

TEORIA DE GRAFOS

ALGORITMO BFS

Cola<Estado> q; q.push(Estado(raiz)); marca[raiz] = true;

TEORIA DE GRAFOS

ALGORITMO BFS

TEORIA DE GRAFOS

ALGORITMO BFS

Cada vez que se visita un nodo, se elimina de la cola y se imprime por pantalla el valor del nodo, para asi, ir indicando el recorrido. Luego, se adiciona a la cola todos los nodos del siguiente nivel y se marcan como visitados antes de comenzar el ciclo de nuevo, en el que se procesan estos nuevos nodos que adicionados a la cola.

TEORIA DE GRAFOS

ALGORITMO BFS

Cada vez que se visita un nodo, se elimina de la cola y se imprime por pantalla el valor del nodo, para asi, ir indicando el recorrido. Luego, se adiciona a la cola todos los nodos del siguiente nivel y se marcan como visitados antes de comenzar el ciclo de nuevo, en el que se procesan estos nuevos nodos que adicionados a la cola.

TEORIA DE GRAFOS

ALGORITMO BFS

TEORIA DE GRAFOS

ALGORITMO BFS

Enlace youtube https://www.youtube.com/watch?v=3VA5brfM68Y

¡Gracias!