3.6.3 En Profundidad

⇐Tema Anterior: 3.6.2 Guiada Por Objetivos(backtrack)
⇒Siguiente Tema: 3.6.4 En Anchura
Regresar al TEMARIO: Matematicas Computacion


Búsqueda en profundidad

Se implementa de forma recursiva, aunque también puede realizarse con una pila. Se utiliza un array val para almacenar el orden en que fueron explorados los vértices. Para ello se incrementa una variable global id (inicializada a 0) cada vez que se visita un nuevo vértice y se almacena id en la entrada del array val correspondiente al vértice que se está explorando.

La siguiente función realiza un máximo de V (el número total de vértices) llamadas a la función visitar, que implementamos aquí en sus dos variantes: representación por matriz de adyacencia y por listas de adyacencia.

int id=0; int val[V];

void buscar() { 

  int k;
  for (k=1; k<=V; k++)
    val[k]=0;
  for (k=1; k<=V; k++)
    if (val[k]==0) visitar(k);

}

void visitar(int k) // matriz de adyacencia { 

  int t;
  val[k]=++id;
  for (t=1; t<=V; t++)
    if (a[k][t] && val[t]==0) visitar(t);

}

void visitar(int k) // listas de adyacencia { 

  struct nodo *t;
  val[k]=++id;
  for (t=a[k]; t!=z; t=t→sig)
    if (val[t→v]==0) visitar(t→v);

}

El resultado es que el array val contendrá en su i-ésima entrada el orden en el que el vértice i-ésimo fue explorado. Es decir, si tenemos un grafo con cuatro nodos y fueron explorados en el orden 3–1−2–4, el array val quedará como sigue:

val[1]=2; // el primer nodo fue visto en segundo lugar val[2]=3; // el segundo nodo fue visto en tercer lugar val[3]=1; // etc. val[4]=4;

Una modificación que puede resultar especialmente útil es la creación de un array “inverso” al array val que contenga los datos anteriores “al revés”. Esto es, un array en el que la entrada i-ésima contiene el vértice que se exploró en i-ésimo lugar. Basta modificar la línea

val[k]=++id; sustituyéndola por

val[++id]=k; Para el orden de exploración de ejemplo anterior los valores serían los siguientes:

val[1]=3; val[2]=1; val[3]=2; val[4]=4;


Google