Project

General

Profile

Algoritmos Elementales de Grafos

Búsqueda de primero en amplitud

Es uno de los algoritmos más simples para la búsqueda en grafos y sirve de arquetipo para varios algoritmos de grafos importantes.

Dado el grafo y un vértice s de origen distinguido, el algoritmo de primero en amplitud sistemáticamente explorara las aristas de G para descubrir cada vértice que es alcanzable desde s. Este algoritmo computa la distancia (el menor número de aristas) entre s y cada vértice alcanzable. También produce un "Árbol de primero en amplitud" con raíz s el cual contiene todos los vértices alcanzables. Para cada vértice v alcanzable por s, el camino simple en el árbol de primero en amplitud desde s a v corresponde al camino más corto desde s hasta v en G, que es, un camino que contiene el menor número de aristas. El algoritmo trabaja tanto en grafos dirigidos como no dirigidos.

El algoritmo de primero en amplitud porque expande las fronteras entre los vértices descubiertos y no descubiertos uniformemente a través de la amplitud de la frontera. esto es, el algoritmo descubre todas las vértices con distancia k desde s antes de descubrir cualquiera con distancia k + 1.

Para mantener el progreso del recorrido, el algoritmo colorea cada vertice de blanco, gris o negro. Todos los vertices empiezan siendo blancos y despues podrian convertirse en grises y finalmente en negros. Un vertice descubierto por primera ves es encontrado durante la busqueda , y es el momento en el que se colorea diferente de blanco. Los vertices grises y negros por lo tanto, tienen que ser descubiertos,pero esta busqueda distingue entre ellos para asegurarse de que la busqueda proceda a manera de primero en amplitud. Si y el vertice u es negro, entonces el vertice v tambien es gris o negro; eso es, todos los verticies adyacentes a un vertice negro debieron haber sido descubiertos. Los vertices grises deben de tener algunos vertices blancos adyacentes; ellos representan la frontera entre los vertices descubiertos y no descubiertos.