RECORRIDO DE GRAFOS

Casi todos los algoritmos para resolver problemas con un grafo examinan o procesan cada vértice y cada arista. La búsqueda primero en amplitud y la búsqueda primero en profundidad son dos estrategias de recorrido que permiten "visitar" de forma eficiente cada vértice y arista exactamente una vez. Por consiguiente, muchos algoritmos basados en tales estrategias se ejecutan en un tiempo que crece linealmente al crecer el tamaño del grafo de entrada.

Generalidades de la búsqueda primero en profundidad

La búsqueda primero en profundidad es una generalización del recorrido general de un árbol. El vértice inicial podría depender del problema o escogerse arbitrariamente. Al igual que con el recorrido de un árbol, resulta útil visualizar la búsqueda primero en profundidad como un viaje alrededor del grafo. La analogía con el recorrido de árboles se ve más claramente en el caso de los grafos dirigidos porque las aristas tienen una dirección, igual que las aristas de los árboles.
El tema de la búsqueda primero en profundidad es: visitar si es posible; si no, retroceder.

Bosquejo de la Búsqueda Primero en Profundidad

BPP(G,v)

{

Marcar v como "visitado"

Para cada vértice w tal que la arista vw está en G

Si w no se ha visitado

BPP(G, w); //es decir, explorar vw, visitar w, explorar desde ahí hasta

//donde sea posible y retroceder de w a v

Si no

"Verificar" vw sin visitar w.

Marcar v como "Terminado"

}

La estrategia primero en profundidad de siempre explorar un camino lo más lejos posible antes de retroceder (y explorar caminos alternos lo más lejos posible antes de retroceder más) tiene el efecto de visitar todos los vértices de G1 antes de pasar a un subgrafo nuevo adyacente a v, en este caso G2 ó G3, después se visitarían todos los vértices de G2 antes de visitar cualquier vértice de G3. Esto es análogo al recorrido de árboles.

Generalidades de la búsqueda primero en amplitud

La búsqueda primero en amplitud es muy diferente de la búsqueda primero en profundidad en términos del orden en el que se descubren los vértices. La mejor forma de visualizar la búsqueda primero en amplitud es como muchas exploraciones simultáneas (o casi simultáneas) que parten de un mismo punto y se extienden de manera independiente.
Veamos cómo funciona la búsqueda primero en amplitud, partiendo del vértice A desde donde se dispersan y exploran en todas las direcciones que permiten las aristas que salen de A.

En la búsqueda primero en amplitud los vértices se visitan en orden de distancia creciente respecto al punto de partida.

Para tratar el algoritmo, se deben hacer las siguientes consideraciones:

Entradas: G = (V, E), un grafo representado por una estructura de listas de adyacencia,

Salidas: Un árbol primero en amplitud, almacenado en el arreglo padre. Ese arreglo se pasa como parámetro y el algoritmo se encarga de llenarlo.

Comentarios: Para una cola Q, suponemos que se usan operaciones del tipo de datos abstracto Cola. El arreglo color[ 1 ],..., color[ n ] denota la situación actual de todos los vértices respecto a la búsqueda. Los vértices no visitados son blancos; los que ya se visitaron pero todavía no se procesan (en la cola) son grises; los que ya se procesaron son negros.

void BPA(ListaInt[] verticesAdya, int n, int s, int[] padre){

int[] color = new int[n+1];
Cola pendiente = crear Cola(n);
Inicializar color [1 ],..., color [n] con blanco.
padre[s] = -1;

color[s] = gris;

MeterEnLaCola(pendiente, s);

while (pendiente no esté vacío)

v = PasarHastaElFrente(pendiente);

SacarDeLaCola(pendiente);

Por cada vértice w de la lista verticesAdya [v];

if (color[w] == blanco)

color[w] = gris;

MeterEnLaCola(pendiente, w);
padre[w]=v; //Procesar la arista vw del árbol. // Seguir con la lista.

// Procesar el vértice v aquí.

color[v] = negro;

return;

}

Análisis de Búsqueda Primero en Amplitud

Suponemos que G tiene n vértices y m aristas, y que la búsqueda llega a todo G. Además, suponemos que cada operación de cola tarda un tiempo constante. Por último, suponemos que el procesamiento que la aplicación efectúa con vértices y aristas individuales tarda un tiempo constante con cada uno; de lo contrario, sería necesario multiplicar los costos apropiados por el tiempo que tarda el procesamiento de cada operación.
Cada arista se procesa una vez en el ciclo while para dar un costo de Θ(m). Cada vértice se coloca en la cola, se saca de ella y se procesa una vez, para dar un costo de Θ(n). Se usa espacio extra para el arreglo color y la cola, y dicho espacio está en Θ(n).