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