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

Recorrido en anchura

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.

Recorrido en profundidad

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 implementación simple en forma recursiva, utilizando globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el orden del recorrido.

ALGORITMO DE BUSQUEDA

Un algoritmo de búsqueda es un algoritmo cuyo propósito es encontrar todos los vértices de un grafo G= (V, E) que satisfacen un propiedad particular. Diferentes variables de un algoritmo de búsqueda aparecen en una gran variedad de problemas. Un vértice está marcado si se sabe que es alcanzable desde el origen. Sea X el conjunto de los vértices marcados  y  Y el conjunto de los vértices no marcados (Y= V- X). Inicialmente X consta de solamente del vértice “r”. Se observa que si uE Y y uV E e, entonces se pueden marcar v. Un algoritmo de búsqueda recorre los vértices marcados en cierto orden. Se escribe ord (u) para indicar el orden de u en el recorrido.

El camino más corto

Una gráfica con pesos es una gráfica en la cual se asignan valores a las aristas y que la longitud de una ruta (camino) en una gráfica de pesos es la suma de los pesos de las aristas en la ruta. Sea w (i, j) el peso de la arista (i, j). En la graficas con pesos, con frecuencias queremos determinar la ruta más corta(es decir, un camino de longitud mínima) entre dos vértices dados.

Algoritmo de Dijkstra

El algoritmo de Dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:

§  Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.

§  Si los pesos de mis aristas son negativos no puedo usar el algoritmo de Dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

Referencias:

Callejas Aboytes Ariana, S. V. (n.d.). Algoritmos de Recorrido y Búsqueda. Retrieved from Instituto Tecnológico de Querétaro, Matemáticas Discretas: http://trabajoenequipoitq.wixsite.com/matematicas-discreta/63-algoritmos-de-bsqueda

Hernandez, B. C. (n.d.). Algoritmos de recorrido y busqueda. Retrieved from SCRIBD: https://www.scribd.com/document/190139396/Algoritmo-de-recorrido-y-busqueda