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