Búsqueda en profundidad

Búsqueda en profundidad

Búsqueda en profundidad

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 uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Análogamente existe el algoritmo de búsqueda en anchura (BFS o Breadth First Search).

Contenido

Pseudocódigo

  • Pseudocódigo para grafos
  DFS(grafo G)
     PARA CADA vertice u ∈ V[G] HACER
             estado[u] ← NO_VISITADO
             padre[u] ← NULO
     tiempo ← 0
     PARA CADA vertice u ∈ V[G] HACER
             SI estado[u] = NO_VISITADO ENTONCES
                     DFS_Visitar(u)
  DFS-Visitar(nodo u)
     estado[u] ← VISITADO
     tiempo ← tiempo + 1
     d[u] ← tiempo
     PARA CADA v ∈ Vecinos[u] HACER
             SI estado[v] = NO_VISITADO ENTONCES
                     padre[v] ← u
                     DFS_Visitar(v)
     estado[u] ← TERMINADO
     tiempo ← tiempo + 1
     f[u] ← tiempo

Arcos DF

Si en tiempo de descubrimiento de u tenemos el arco (u,v):

i. Si el estado de v es NO_VISITADO, entonces (u,v) ∈ DF.

Véase también

  • Árbol (estructura de datos)


  • Lema: Un grafo dirigido es cíclico si y sólo si al ejecutar DFS(G) produce al menos un arco hacia atrás.

Referencias

Obtenido de "B%C3%BAsqueda en profundidad"

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • 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 — 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

  • Profundidad de línea — Saltar a navegación, búsqueda La profundidad de línea es un concepto de mercadotecnia para referirse la variedad total que se ofrece de un determinado producto. Se utiliza para determinar cuán capaz es una empresa para cubrir la demanda de un… …   Wikipedia Español

  • Profundidad de pasada — Saltar a navegación, búsqueda La profundidad de pasada es la anchura de corte que tiene una herramienta de torno o de fresadora. Se refleja por el ancho de la viruta. Su valor está en conconancia con la cantidad de material que se tenga que… …   Wikipedia Español

  • Profundidad de campo — Saltar a navegación, búsqueda Ejemplo de profundidad de campo, sólo la línea central aparece enfocada, el resto no …   Wikipedia Español

  • Profundidad de color — Saltar a navegación, búsqueda Paleta de colores. La profundidad de color o bits por pixel es un concepto de la computación gráfica que se refiere a la cantidad de bits de información necesarios para representar el color de un píxel en una imagen… …   Wikipedia Español

  • Profundidad — Saltar a navegación, búsqueda Para otros usos de este término, véase Profundidad (desambiguación). Se denomina profundidad a la distancia de un elemento con respecto un plano horizontal de referencia cuando dicho elemento se encuentra por debajo… …   Wikipedia Español

  • Profundidad (Misiones) — Saltar a navegación, búsqueda Profundidad Bandera …   Wikipedia Español

  • Profundidad (desambiguación) — Saltar a navegación, búsqueda Profundidad puede referirse a: Profundidad, unidad de longitud. El municipio argentino de Profundidad, en la provincia de Misiones, Argentina; Obtenido de Profundidad (desambiguaci%C3%B3n) Categoría:… …   Wikipedia Español

  • Profundidad de periscopio — Saltar a navegación, búsqueda Profundidad de Periscopio es la profundidad mínima necesaria para levantar la cabeza focal del mástil de observación o de ataque sobre la superficie del agua, dependiendo del largo del vástago y del estado del mar.… …   Wikipedia Español

Compartir el artículo y extractos

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