5.3 Algoritmos de recorrido y búsqueda

• 5.3 ALGORITMOS DE RECORRIDO Y BÚSQUEDA

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodos de salida.existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura y el recorrido en profundidad.

Así, para recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado.hay dos formas.

• Recorrido en profundidad (DFS)
• Recorrido en anchura (BFS)

Algoritmo BFS

El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial.

Para la implementación de este algoritmo se utiliza

globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere también un vector de cola auxiliar para gestionar los vértices no visitados.

En muchos casos es necesario ejecutar este algoritmo empezando en los nodos más alejados del nodo escogido como nodo inicial.



Algoritmo DFS

El algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más recientemente. De esta forma se va "profundizando" en el grafo, es decir, alejándose progresivamente del nodo inicial [2]. Esta estrategia admite una complementación simple en forma re-cursiva, utilizando global mente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el orden del recorrido.

A lo Ancho (BEA)
 
Se comienza en el vértice inicial (vértice con índice 1) y se marca como vértice activo, a diferencia con la BEP ahora se visitan en orden creciente de índice todos los vecinos del vértice activo antes de pasar al siguiente. Hasta que todos los vértices hayan sido visitados, en cada paso se van visitando en orden creciente de índice todos los vecinos del vértice activo. Cuando se han visitado todos los vecinos del vértice activo, se toma como nuevo vértice activo el primer vértice X visitado después del actual vértice activo en el desarrollo del algoritmo.

ALGORITMO BEA:

Sea G = (V, A) un grafo conexo, V' = V un conjunto de vértices, A' un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:

Se introduce el vértice inicial en P y se elimina del conjunto.

Mientras V' no sea vacío repetir los puntos 3 y 4. En otro caso parar.

Se toma el primer elemento de P como vértice activo.

Si el vértice activo tiene algún vértice adyacente que se encuentre en V':
Se toma el de menor índice.
Se inserta en P como último elemento.
Se elimina de V'.
Se inserta en A' el arco que le une con el vértice activo.
Si el vértice activo no tiene adyacentes se elimina de P.




























Se comienza en el vértice inicial (vértice con índice 1) que se marca como vértice activo. Hasta que todos los vértices hayan sido visitados, en cada paso se avanza al vecino con el menor índice siempre que se pueda, pasando este a ser el vértice activo. Cuando todos los vecinos al vértice activo hayan sido visitados, se retrocede al vértice X desde el que se alcanzó el vértice activo y se prosigue siendo ahora X el vértice activo.

ALGORITMO BEP:

Sea G = (V, A) un grafo conexo, V' = V un conjunto de vértice, A'un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:

Se introduce el vértice inicial en P y se elimina del conjunto V'.

Mientras V' no sea vacío repetir los puntos 3 y 4. En otro caso parar.

Se toma el último elemento de P como vértice activo.
Si el vértice activo tiene algún vértice adyacente que se encuentre en V':
Se toma el de menor índice.
Se inserta en P como último elemento.
Se elimina de V'.
Se inserta en A' el arco que le une con el vértice activo.
Si el vértice activo no tiene adyacentes se elimina de P. 

5.3.1 EL CAMINO MAS CORTO
El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de la siguiente generalización:
· El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo. (Algoritmo Floyd-Warshall)


Floyd-Warshall


En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica.


El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V3 comparaciones (esto es notable considerando que pueden haber hasta V2 aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.


· El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.
· El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo. (Algoritmo Dijkstra)


Algoritmo Dijkstra:

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas interacciones bajarían el costo general del camino al pasar por una arista con costo negativo).




5.3.2 A LO ANCHO

RECORRIDO EN ANCHURA

“En Ciencias de la Computación, Búsqueda en anchura (en inglés BFS – Breadth First Search) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.”

 

Un recorrido en anchura se refiere a recorrer un grafo por niveles, es decir, partiendo de un nodo inicial recorro todos sus vecinos, posteriormente los vecinos de los vecinos hasta que todos los nodos hayan sido visitados.

5.3.3 EN PROFUNDIDAD

“Una Búsqueda en profundidad (en inglés DFS o Depth First Search) 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 (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.”

Un recorrido en profundidad es que partiendo de un nodo inicial, visite toda una rama, luego otra hasta que todos los nodos hayan sido visitados.

 

Referencias:

https://juanset19.wordpress.com/2013/08/10/recorrido-en-anchura-y-en-profundidad-de-un-grafo-representado-por-una-matriz/

http://equipo1mditq.blogspot.mx/2014/11/631-el-camino-mas-corto.html   

http://trabajoenequipoitq.wixsite.com/matematicas-discreta/63-algoritmos-de-bsqueda