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 articulo explicaremos la búsqueda por anchura (BFS). A continuación se muestra el algoritmo de la búsqueda por anchura en un grafo representado por medio de listas de adyacencias. En dicho algoritmo se usa una cola para almacenar los nodos adyacentes al actual y guardarlos para continuar con la búsqueda. La siguiente implementación del recorrido por anchura para un grafo completamente conectado (existe al menos un camino entre cualquier par de vértices en el grafo) y para un grafo que no lo esta. int visitado[1000]; vector<list<int> > grafo(1000); // algoritmo para grafo completamente conectado void BFS(int v) { // v es el nodo de inicio del recorrido list<int> cola; // cola de adyacentes list<int>::iterator nodo_actual, aux, fin; visitado[v] = 1; // marcamos como visitado el nodo de inicio cola.push_back(v); // metemos inicio a la cola while (!cola.empty()) { nodo_actual = cola.front(); // sacar nodo de la cola cola.pop_front(); aux = grafo[nodo_actual].begin(); //posicionar iteradores para //lista de ady fin = grafo[nodo_actual].end(); while (aux != fin) { // recorrer todos los nodos ady a nodo actual if (!visitado[*aux]) { // añadir a la cola solo los no visitados visitado[*aux] = 1; // marcarlos como visitados cola.push_back(*aux); // añadirlos a la cola // aqui podriamos añadir codigo para hacer algo mientras // recorremos el grafo } aux++; // avanzar al siguiente adyacente del nodo actual } } } // algoritmo para grafo que no esta completamente conectado void BFS2() { for (int i = 0; i < nvert; i++) if (!visitado[i]) BFS(i); } En esta implementación podrán ver que primero se visitan los nodos o vértices que fueron visitados primero. Por ejemplo para el grafo de la figura si comenzamos la búsqueda por el nodo cero (0). 0. Inicio BFS(0) nodoActual = -1, cola = [0] 1. Sacamos el primer nodo de la cola nodoActual = 0, cola = [] 2. 0 visitara a BFS(1) y BFS(3) nodoActual = 0, cola = [1, 3] 3. Sacamos el primer nodo de la cola nodoActual = 1, cola = [3] 4. 1 visitara a BFS(2) y BFS(3) pero 3 ya fue visitado nodoActual = 1, cola = [3, 2] 5. Sacamos el primer nodo de la cola nodoActual = 3, cola = [2] 6. 3 visitara a BFS(2) y BFS(4) pero 2 ya fue visitado nodoActual = 3, cola = [2, 4] 7. Sacamos el primer nodo de la cola nodoActual = 2, cola = [4] 8. 2 visitara a BFS(4) pero 4 ya fue visitado nodoActual = 2, cola = [4] 9. Sacamos el primer nodo de la cola nodoActual = 4, cola = [] 10. El algoritmo termina por la cola esta vacía Para practicar con este tipo de busqueda puedes utlizar uno de los siguientes enlaces: HackerEarth Problems - Breadth First Search CP3 - Chapter 4. Graph - Breadth First Search