Búsqueda en anchura

Búsqueda en anchura

Para otros usos de este término, véase Búsqueda.

En Ciencias de la Computación, 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 se exploran 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 árbol sistemá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 versiones.

Procedimiento

  • Dado un vértice fuente s, Breadth-first search sistemáticamente explora los vértices de G para “descubrir” todos los vértices alcanzables desde s.
  • Calcula la distancia (menor número de vértices) desde s a todos los vértices alcanzables.
  • Después produce un árbol BF con raíz en s y que contiene a todos los vértices alcanzables.
  • El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más corto medido en número de vértices.
  • Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k, sólo tras haber llegado a todos los nodos a distancia k-1.

Pseudocódigo

  • La nomenclatura adicional utilizada es: Q = Estructura de datos cola


  BFS(grafo G, nodo_fuente s) 
  { 
     // recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
     // distancia INFINITA y padre de cada nodo NULL
     for u ∈ V[G] do
     {
        estado[u] = NO_VISITADO;
        distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
        padre[u] = NULL;
     }
     estado[s] = VISITADO;
     distancia[s] = 0;
     Encolar(Q, s);
     while !vacia(Q) do
     {
        // extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
        u = extraer(Q);
        for  v ∈ adyacencia[u]  do
        {
           if estado[v] == NO_VISITADO then
           {
                estado[v] = VISITADO;
                distancia[v] = distancia[u] + 1;
                padre[v] = u;
                Encolar(Q, v);
           }
        }
     }
  }
  *Falta recorrer vertices no adyacentes directa o indirectamente al vertice origen "s",
pues cola queda vacia sin los adyacentes restantes.
  • El tiempo de ejecución es O(|V|+|E|). Nótese que cada nodo es puesto a la cola una vez y su lista de adyacencia es recorrida una vez también.

Referencias

Obtenido de "B%C3%BAsqueda en anchura"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Búsqueda en anchura — En Ciencias de la Computación, Búsqueda en anchura (BFS o Breadth first search en inglés) 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… …   Enciclopedia Universal

  • Búsqueda — Saltar a navegación, búsqueda Búsqueda puede hacer referencia a: Busca, acción de buscar. Motor de búsqueda, sistema informático que indexa archivos almacenados en servidores web gracias a su «spider» (o Web crawler). Búsqueda binaria o Algoritmo …   Wikipedia Español

  • Búsqueda en profundidad — Saltar a navegación, búsqueda Para otros usos de este término, véase Búsqueda. Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no… …   Wikipedia Español

  • Búsqueda en profundidad — Un recorrido en profundidad (en inglés DFS Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme. Su manera de funcionar se basa en ir expandiendo cada una de los nodos… …   Enciclopedia Universal

  • Búsqueda de respuestas — Para otros usos de este término, véase Búsqueda. La búsqueda de respuestas, llamado en inglés Question Answering (QA) es un tipo de recuperación de la información. Dada una cierta cantidad de documentos (tales como World Wide Web), el sistema… …   Wikipedia Español

  • Algoritmo de búsqueda A* — Ejemplo de aplicación del algoritmo A*. El algoritmo de búsqueda A* (pronunciado A asterisco o A estrella ) se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y… …   Wikipedia Español

  • Árbol binario de búsqueda — Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática. Contenido 1 Descripción 2 Operaciones 2.1 Búsqueda …   Wikipedia Español

  • Búsquedas no informadas — Saltar a navegación, búsqueda Contenido 1 Introducción a las búsquedas no informadas 2 Representación del espacio de estados 3 La búsqueda en profundidad …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Árbol (informática) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.