En Ciencias

Recorridos en Grafos.
El recorrido de un grafo, o su navegación, se realiza siguiendo las relaciones de adyacencia, es decir a través de las conexiones entre los nodos. En otras palabras desde un vértice se puede ir solamente a uno de sus adyacentes. Recorrerlo significa pasar una y sólo una vez por cada nodo, cumpliendo en él con la tarea que se deba hacer según el caso; dicha tarea se llamarágenéricamente Visitar.

Según la manera en que se vayan recorriendo los adyacentes de cada vértice del grafo podemos distinguir:
1. Recorrido en Profundidad
2. Recorrido en Anchura

1. Recorrido en Profundidad
La estrategia en la que se basa este recorrido es la misma que aplicamos en el recorrido en preorden de los árboles. Dado un digrafo como el de la figura, la idea es quepartiendo de uno de los vértices avanzar lo más lejos que se pueda, a través de uno de los adyacentes (por ejemplo el primero de ellos). Una vez que no se puede avanzar más, se continúa a partir del próximo adyacente del último visitado. Para el ejemplo mostrado si comenzamos el recorrido a partir del vértice rotulado con la A, este recorrido nos permitiría visitar los restantes vértices en elsiguiente orden: A, B, C, D, E, F. Analicemos este recorrido. Comenzamos con el vértice rotulado con A y tomando como convención que de los adyacentes a A elegimos el primero, luego visitamos el vértice rotulado con B. Una vez alcanzado el vértice con rótulo B, pasamos a su únicoadyacente el rotulado con C. De los dos adyacentes de éste, los vértices rotulados con D y E respectivamente,optamos por el primero visitando de esta manera al que tiene rótulo D. En este punto no podemos avanzar más pues D no tiene adyacentes, razón por la cual retomamos los adyacentes del vértice visitado inmediatamente antes. Como ese vértice fue el rotulado con C, continuamos el recorrido con el próximo de sus adyacentes el rotulado con E. Una vez visitado el vértice con rótulo E, continuamos elrecorrido por su primer adyacente, el vértice con rótulo F. Visitamos F y nuevamente como éste no tiene adyacentes debemos retornar y continuar con los adyacentes a C. Dado que para nuestro ejemplo el vértice rotulado con E era el último de los adyacentes a C, debemos continuar explorando los adyacentes que dejamos pendientes al pasar a C. En otras palabras debemos tomar el próximo adyacente al vérticecon rótulo B. En el digrafo ejemplo, B tenía un único adyacente, por lo cual esa instancia ya está completa. El recorrido por consiguiente debería retomar los adyacentes a Aa partir del último explorado. Siendo que de estos vértices el único explorado fue el rotulado con B, el recorrido debería considerar a C que es el próximo de sus adyacentes. En este punto debemos detenernos en el hecho deque ya visitamos dicho vértice. Si lo que nosotros estamos planteando es recorrer todos los vértices del digrafo, obviamente pasando por cada vértice una sola vez, no debemos visitarlo nuevamente. Además como ya lo visitamos, también hicimos lo propio con todos los demás vértices que se pueden alcanzar a partir del mismo. Situación similar a la anterior es la que enfrentamos al intentar elrecorrido con el próximo de los adyacentes al vértice con rótulo A, el vértice con rótulo E. Este vértice ya fue visitado por lo cual deberíamos descartarlo y continuar con el siguiente. Como este vértice es el último de los adyacentes al rotulado con A, finalizamos nuestro recorrido. La situación anterior nos lleva a plantearnos la necesidad de llevar un control o un registro de los vértices que se hanido visitando previamente para no volver a visitarlos. Contar con un registro tal, nos permite detectar la presencia de ciclos en el grafo que estamos recorriendo. Si en el digrafo del ejemplo hubiera una arista con origen en el vértice rotulado con C y destino en el de rótulo A, al recorrerlo quedaríamos atrapados en el ciclo ABC. Esto lo evitamos al saber que el vértice con rótulo A ya...