Existen dos algoritmos básicos para recorrer un grafo o buscar un nodo en particular, la búsqueda por anchura o BFS y la búsqueda por profundidad o DFS. En este artículo explicaremos la búsqueda por profundidad (DFS).
El algoritmo de la búsqueda por profundidad se puede hacer modificando el anterior (Parte 3.1 BFS) en la parte que usa una cola y usar una pila. Otra forma de implementarla es usando recursividad, a continuación se muestran ambos enfoques así como la rutina para hacer la búsqueda en grafos que no están completamente conectados.
A continuación se presenta el listado con la implementación de la búsqueda por profundidad o DFS. También se ha añadido en la versión recursiva un contador que marca el orden en el que fueron visitados los nodos del grafo, dicho orden es muy útil al implementar otros algoritmos de grafos.
Implementación DFS (usando una pila)
int visitado[1000];
vector<list<int> > grafo(1000);
void DFS(int v) { //v es el nodo de inicio del recorrido
list<int> pila; //pila de nodos adyacentes
list<int>::iterator nodo_actual, aux, fin;
visitado[v] = 1; //marcar como visitado el nodo de inicio
pila.push_back(v);
while (!pila.empty()) { //mientras no se vacie la pila de adyacentes
nodo_actual = pila.back();
//aqui podriamos marcar el orden en que se visitaron
pila.pop_back();
aux = grafo[nodo_actual].begin(); // posicionar iteradores para
// lista adyacente
fin = grafo[nodo_actual].end();
while (aux != fin) { //recorrer todos los adyacente al nodo actual
if (!visitado[*aux]) { //añadir a la pila solo los no visitados
visitado[*aux] = 1;
pila.push_back(*aux);
//aqui podemos añadir código para hacer algo mientras
//realizamos el recorrido
}
aux++; //avanzar al siguiente adyacente del nodo actual
}
}
}
Implementacion DFS (recursiva)
int visitado[1000];
vector<list<int> > grafo(1000);
void DFS(int v) {
list<int>::iterator aux, fin; //iteradores para lista de ady
visitado[v] = 1; //marcar como visitado
//aqui se podria marcar el orden en que fueron visitados
aux = grafo[v].begin(); //posicionar los iteradores para lista de ady
fin = grafo[v].end();
while (aux != fin) {
if (!visitado[*aux])
DFS(*aux); //no se necesita marcar porque *aux se convierte en v
aux++; //avanzar al siguiente adyacente de v
}
}
//esta es la version para grafos que no estan completamente conectados
void DFS2() {
int i;
for (int i = 0; i < nvert; i++) //buscar un nuevo nodo de
if (!visitado[i]) //inicio que no ha sido visitado
DFS(i);
}
En esta implementación podrán ver que primero se visitan los nodos o vértices que fueron visitados al final, en este caso los números que se encuentran en la pila tienen como primer número al último que fue ingresado.
Por ejemplo para el grafo de la figura si comenzamos la búsqueda por el nodo cero (0).
0. Inicio DFS(0)
nodoActual = -1, pila = [0]
1. Sacamos el primer nodo de la pila
nodoActual = 0, pila = []
2. 0 visitara a DFS(1) y DFS(3)
nodoActual = 0, pila = [1, 3]
3. Sacamos el primer nodo de la pila
nodoActual = 3, pila = [1]
4. 3 visitara a DFS(2) y DFS(4)
nodoActual = 3, pila = [1, 2, 4]
5. Sacamos el primer nodo de la pila
nodoActual = 4, pila = [1, 2]
6. 4 no visita a ningun nodo
nodoActual = 4, pila = [1, 2]
7. Sacamos el primer nodo de la pila
nodoActual = 2, pila = [1]
8. 2 visitara a DFS(4) pero 4 ya fue visitado
nodoActual = 2, pila = [1]
9. Sacamos el primer nodo de la pila
nodoActual = 1, pila = []
10. El algoritmo termina por la pila esta vacía
En el caso de la implementación recursiva deberán hacerla correr con un ejemplo de grafo para poder analizar la pila, cuando las funciones se llaman recursivamente verán que no se llama a una sin que termine la última en ser llamada y a su vez esperará hasta que todas las funciones llamadas por la otra función sean terminadas.
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int visitado[1000];
vector<list<int> > grafo(1000);
void DFS(int v) {
list<int>::iterator aux, fin; //iteradores para lista de ady
visitado[v] = 1; //marcar como visitado
//aqui se podria marcar el orden en que fueron visitados
cout << v << " fue visitado" << endl;
aux = grafo[v].begin(); //posicionar los iteradores para lista de ady
fin = grafo[v].end();
while (aux != fin) { // este ciclo extra esta para imprimir los siguientes nodos
cout << '\t' << (*aux) << " sera visitado por " << v << endl;
aux++; //avanzar al siguiente adyacente de v
}
aux = grafo[v].begin(); //posicionar los iteradores para lista de ady
fin = grafo[v].end();
while (aux != fin) {
if (!visitado[*aux])
DFS(*aux); //no se necesita marcar porque *aux se convierte en v
aux++; //avanzar al siguiente adyacente de v
}
}
int main() {
// conectamos el grafo
grafo[0].push_back(1);
grafo[0].push_back(3);
grafo[1].push_back(2);
grafo[1].push_back(3);
grafo[2].push_back(4);
grafo[3].push_back(2);
grafo[3].push_back(4);
// llamamos a la funcion DFS
DFS(0);
}
Para practicar con este tipo de busqueda puedes utlizar uno de los siguientes enlaces:
HackerEarth Problems - Depth First Search
CP3 - Chapter 4. Graph - Depth First Search