Algoritmos De Recorrido

Introducción
En esta unidad veremos sobre los recorridos que pueden hacerse a los algoritmos que albergan listas en ellos.

Estos algoritmos se pueden utilizar para buscar u ordenar, ya que como su nombre lo dice realizan un recorrido por la lista y con ello podemos utilizarlo para distintas cosas.

Además veremos acerca de los algoritmos de recorrido de árbol y los de grafos, así desde quee slo que son y un poco de como utilizarlos.

Tambien sabremos sobre que son los algoritmos de búsqueda de profundidad y los algoritmos de búsqueda de anchura.

 
Algoritmos de recorrido
Ya que las colas son FIFO(First in - First Out) el Recorrido se hace sacando el primer dato que se inserto hasta que llegue al extremo llamado Final.

En un principio se compara para saber si tiene algúndato en la Cola, si no es así desplegara “Cola Vacía…”. De otra forma compara si Frente es mayor o igual a Final, de esta forma simplemente hace un Recorrido lineal como los anteriores. De otra forma usar Max como bandera para saber cuando empezar a contar de 0 a Final (Ya que sabemos que el Frente después del nodo Final).
Esta es una manera de hacer el recorrido.

Arboles
Se llama recorridode un árbol al proceso que permite acceder una sola vez a cada uno de los nodos del árbol para examinar el conjunto completo de nodos.

Primeramente se ven los algoritmos para construir el árbol sintáctico, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está sintácticamente correcta cuando esta dada en prefijo o posfijo.
Alvisitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue: Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T. Si T consiste de un sólo nodo n,entonces, n es el listado preorden, post-orden y en-orden del árbol T.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz
• recorrer el subárbol izquierdo
• recorrer el subárbol derecho
Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.




Recorrido en Profundidad (Arboles):El proceso exige alcanzar las profundidades de un camino desde la raíz hacia el descendiente mas lejano del primer hijo, antes de proseguir con el segundo. Recorrido en Anchura: el proceso se realiza horizontalmente desde la raíz a todos su hijos antes de pasar con la descendencia de alguno de ellos.
Grafos:
Un grafo, representa un conjunto de nodos unidos en una red. Si dos nodos estánunidos, al viajar de uno a otro se considerara sucesor el nodo al que nos movemos, y predecesor el nodo del que venimos. Además, normalmente existirá un coste vinculado al desplazamiento entre nodos. Un algoritmo de búsqueda tratará, de encontrar un camino óptimo entre dos nodos como por ejemplo un camino que minimice el coste de desplazamiento, o el número de pasos a realizar.

Se utilizan enprogramas que precisan aplicar sistemáticamente un tratamiento a todos los vértices de un grafo (visitar todos los vértices).

• recorrido en profundidad
• recorrido en anchura
• recorrido por ordenación topológica

Característica común: uso de conjuntos para almacenar los vértices visitados (a diferencia de en los árboles, a un mismo nodo puede accederse por distintos caminos, y hay que evitarvisitas reiteradas).

Recorrido en Profundidad (Grafos):
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...