Recorridos de un Grafo

Los recorridos de un grafo son de suma importancia, ya que para encontrar un dato en este tipo de estructura, se puede hacer un poco complejo, dependiendo de como este estructurado el grafo, ya que si por ejemplo un nodo del grafo puede estar conectado con el mismo, este tipo de enlace puede enciclar el programa y nunca poder recorrer todos los demás elementos del grafo. En esta sesión vamos a ver los dos tipo de recorridos de un grafo.

Recorrido en profundidad
Trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente. La búsqueda en profundidad empieza por un vértice V. del grafo G; no visitado; así hasta que no haya mas vértice adyacentes no visitados.

Representación gráfica de un recorrido de profundidad en un grafo

Recorrido en anchura
Supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida. Este método comienza visitando el vértice de partida A, para continuación visitar los adyacentes que no estuvieron ya visitados. Así sucesivamente con los adyacentes. Este método utiliza una cola como estructura auxiliar en la que se mantienen los vértices que se vayan a procesar posteriormente.

Representación gráfica de recorrido en anchura de un grafo

Por lo tanto, recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado.

Fuentes:
Presentación de los grafos