ALGORITMOS DE RECORRIDO Y BUSQUEDA

 ALGORITMOS DE RECORRIDO Y BÚSQUEDA.

En ciencias de la computación, es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.)

Peter Hart, Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International) describieron por primera vez el algoritmo en 1968. Se trata de una extensión de la Edsger Dijkstra al goritmo de 1959.

Existen algunas maneras útiles en las cuales se pueden ordenar sistemáticamente los nodos de un árbol. Los más importantes son: preorden, post-orden y en-orden.

Estos tienen tres tipos de actividades comunes:

1. Visitar el nodo raíz

2. Recorrer el subárbol izquierdo

3. Recorrer el subárbol derecho

Estas tres actividades llevadas acabo en distinto orden, crean los distintos recorridos del árbol.

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

1. Visite la raíz

2. Atraviese el sub-árbol izquierdo

3. Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo

2. Visite la raíz

3. Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.Atraviese el sub-árbol izquierdo

2.Atraviese el sub-árbol derecho

3.Visite la raíz

Algoritmo BFS

El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial. Para la implementación de este algoritmo se utiliza globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere también un vector de cola auxiliar para gestionar los vértices no visitados. En muchos casos es necesario ejecutar es te algoritmo empezando en los nodos más alejados del nodo escogido como nodo inicial.

A LO ANCHO

RECORRIDO EN ANCHURA

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.

Un recorrido en anchura se refiere a recorrer un grafo por niveles, es decir, partiendo de un nodo inicial recorro todos sus vecinos, posteriormente los vecinos de los vecinos hasta que todos los nodos hayan sido visitados.

Algoritmo DFS

El algoritmo de recorrido en  profundidad o DFS, explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más recientemente. De esta forma se va "profundizando" en el grafo, es decir, alejándose progresivamente del nodo inicial. Esta estrategia admite una complementación simple en forma re-cursiva, utilizando globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el orden del recorrido.

EN  PROFUNDIDAD

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 (teoría de grafos) 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.

Un recorrido en profundidad es que partiendo de un nodo inicial, visite toda una rama, luego otra hasta que todos los nodos hayan sido visitados.

BIBLIOGRAFIA

(2014).TEORIADEGRAFOS.2017,deblogspotSitioweb:http://9relaciones.blogspot.mx/2014/11/teoria-de-grafos.html

AlexOrtegón.TEORÍADEGRAFOS.2017,deblogspotSitioweb:http://mate-discretasj2.blogspot.mx/p/blog-page.html