Instituto Tecnológico de Querétaro
Matemáticas Discretas
6.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 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.
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.
En Profundida (BEP)
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.
