B SQUEDA ANCHURA

BÚSQUEDA ANCHURA  (BEA)
        Se comienza en el vértice inicial (vértice con índice 1) y se marca como vértice activo, a  diferencia con la BEP ahora se visitan en orden creciente de índice todoslos vecinos del vértice activo antes de pasar al siguiente. Hasta que todos los vértices hayan sido visitados, en cada paso se van visitando en orden creciente de índice todos los vecinos del vérticeactivo. Cuando se han visitado todos los vecinos del vértice activo, se toma como nuevo vértice activo el primer vértice X visitado después del actual vértice activo en el desarrollo del algoritmo.ALGORITMO BEA:
    Sea G = (V, A) un grafo conexo, V’ = V un conjunto de vértices, A’ un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:
1. Se introduce el vértice inicialen P y se elimina del conjunto.
2. Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.
3. Se toma el primer elemento de P como vértice activo.
4. Si el vértice activo tiene algúnvértice adyacente que se encuentre en V’:
Se toma el de menor índice.
Se inserta en P como último elemento.
Se elimina de V’.
Se inserta en A’ el arco que le une con el vértice activo.
Si el vérticeactivo no tiene adyacentes se elimina de P.

 Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles).Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos seexploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.
Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbolsistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística.
Si las aristas tienen pesos negativos aplicaremos el algoritmo de Bellman-Ford en alguna de sus dos...