5.3 Algoritmos de recorrido y búsqueda

5.3 Algoritmos de recorrido y búsqueda

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

Pre orden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en pre orden, 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

Se llama recorrido de un árbol al proceso que permite accede una vez a cada uno de los elementos de un árbol para examinar el conjunto completo. Primero se ven los algoritmos para construir el árbol, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está correcta cuando está dada en prefijo o posfijo.

Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.

·         Recorrido en PREFIJO:

     1.  Visitar la raíz

     2.  Recorrer el subárbol izquierdo en prefijo

     3.  Recorrer el subárbol derecho en prefijo

·         Recorrido SUFIJO:

     1.  Recorrer el subárbol izquierdo en sufijo

     2.  Visitar la raíz

     3.  Recorrer el subárbol derecho en sufijo

·          Recorrido en POSFIJO:

     1.  Recorrer el subárbol izquierdo en postfijo

     2.  Recorrer el subárbol derecho en postfijo 

     3.  Visitar la raíz

5.3.1 El camino más corto

En la Teoría de Grafos, uno de los problemas más conocido es el del camino más corto.

El problema consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

En el grafo siguiente, Luisa y Pedro tienen que encontrar el camino más corto (en el sentido de menos “pesado”) entre los vértices a y e.

La solución es el camino abce.

5.3.2 A lo ancho

En ciencias de la computación, A *es un algoritmo informático que se utiliza amplia mente 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.

5.2.3 En profundidad

En ciencias de la computación, recorrido del grafo es el problema de visitar todos los nodos en un gráfico de una manera particular, actualización y / o control de sus valores a lo largo del camino, recorrido del árbol es un caso especial del recorrido del grafo. 

Una búsqueda en profundidad (DFS) es un algoritmo para recorrer un grafo finito. DFS visitas los nodos secundarios antes de visitar los nodos del mismo nivel, es decir, que atraviesa la profundidad de cualquier camino en particular antes de explorar su amplitud.

El algoritmo comienza con un nodo “raíz” elegida, entonces iterativamente transiciones desde el nodo actual a una, el nodo no visitado adyacente, hasta que ya no puede encontrar un nodo inexplorado para la transición a partir de su ubicación actual.

Fuentes:

·       * Karen Nohemi Morales Galindo (s.f), 6.3 Algoritmos de recorrido y búsqueda, recuperado de: https://sites.google.com/site/matematicasmoralesgalindo/6-3-algoritmos-de-recorrido-y-busqueda

·       * 3.1. El camino más corto (s.f), de DEMO E-DUCATIVA CATEDU, recuperado de: http://e-ducativa.catedu.es/44700165/aula/archivos/repositorio//4500/4724/html/31_el_camino_ms_corto.html

* Alejandro De J. López Ortegón, Esmeralda Zurita Gallegos, Cesar A. Pech Interian, Russel Chuc Aguilar, Alinda E. Chan May, Micaela Baas Dzul (s.f), Teoria de grafos, recuperado de: http://mate-discretasj2.blogspot.mx/p/blog-page.html