El algoritmo Breadth-first Search(BFS) sirve para recorrer todos lo nodos o vértices de un árbol o de un grafo de manera sistemática.
Es adecuado especialmente para resolver problemas de
optimización, en los que se deba elegir la mejor solución entre varias posibles.
Al igual
que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer
vértice activo. En el siguiente paso se etiquetan como visitados todos los vecinos del
vértice activo que no han sido etiquetados. Se continúa etiquetando todos los vecinos de
los hijos de v (que no hayan sido visitados aún).
En este proceso nunca se visita un
vértice dos veces por lo que se construye un grafo sin ciclos, que será un árbol
generador de la componente conexa que contiene a v.
Sea G(V, E) un grafo conexo y v un vértice de V.
El algoritmo de búsqueda en anchura
puede detallarse así:
- Designamos a v como vértice activo y como raíz del árbol generador T que se construirá. Se le asigna a v la etiqueta 0.
- Sea i=0 y S={v}.
- Hallar el conjunto M de todos los vértices no etiquetados que son adyacentes a algún vértice de S.
- Si M es vacío el algoritmo termina. En caso contrario, se etiquetan todos los vértices de M con i+1, se añaden a T las aristas entre cada vértice de S y su vecino en M y se hace S=M.
- i=i+1 y volver al paso 3. Al terminar el proceso se habrá construido un árbol generador del grafo inicial.
Pseudo-código formal:
No hay comentarios:
Publicar un comentario