Grafos

Grafos: Búsquedas
Existen dos técnicas básicas para recorrer los vértices de un grafo, la búsqueda por profundidad (DFS) y la búsqueda por anchura (BFS). La búsqueda por profundidad se usa cuando queremos probar si una solución entre varias posibles cumple con ciertos requisitos como sucede en el problema del camino que debe recorrer un caballo para pasar por las 64 casillas del tablero. Labúsqueda por anchura se usa para aquellos algoritmos en donde resulta crítico elegir el mejor camino posible en cada momento como sucede en dijkstra.
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.El siguiente listado contiene la 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.
//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>::iteratornodo_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();
    //posicionar iteradores para lista de ady
    aux = grafo[nodo_actual].begin();
    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 nodoactual
    }     
  }
}
//algoritmo para grafo que no esta completamente conectado
void BFS2()
{
  int i;
  for(i = 0; i < nvert; i++)
    if(!visitado[i])
      BFS(i);
}
Listado 7. BFS o recorrido por anchura
Para que el código anterior funcione, se deben declarar de manera global el grafo y el arreglo de visitados. El arreglo de visitados debe contener ceros antes de iniciar elrecorrido en el grafo. Dentro del ciclo que añade los vértices recién visitados a la cola puede añadirse código para hacer algo mientras se recorre el grafo, un ejemplo de esto último lo pueden encontrar en mi solución del problema 10009, donde se usa para asignar un nivel a cada ciudad y luego implementar un algoritmo Adhoc para encontrar un camino entre dos ciudades.
El algoritmo de la búsquedapor profundidad se puede hacer modificando el anterior 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 haañ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.
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 deinicio
  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 ady
    fin = grafo[nodo_actual].end();
    while(aux != fin) ...