6.3.2.- ALGORITMOS DE RECORRIDO Y BÚSQUEDA A LO ANCHO

09.12.2015 16:12

La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. 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.