Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Busca em profundidade

(Veja Depth-first search na Wikipedia.)

Este capítulo discute uma segunda implementação clássica do algoritmo genérico de busca.  Nessa implementação, o conjunto de vértices ativos é administrado como uma pilha (= stack):  cada iteração escolhe o vértice ativo que foi marcado mais recentemente.  O resultado dessa política é conhecido como busca em profundidade (= depth-first search = DFS). 

O algoritmo genérico pode então ser reescrito assim:

1 2 3 4 5 6 7 8

enquanto a pilha não está vazia faça seja  v  o vértice no topo da pilha se A(v) não está vazio então retire um arco (v,w) de A(v) então se w não está marcado então então marque w então então coloque w no topo da pilha senão retire v do topo da pilha

Exercícios

1. A tabela abaixo define um grafo com vértices A, B, C, D, E, F.   Uma busca em profundidade é executada a partir do vértice F e os vértices são encontrados na ordem   F,   A,   D,   C,   E,   B.

   ponta inicial		F	F	A	B	E	A	D	A
   arco		a	b	c	d	e	f	g	h
   ponta final		A	D	B	E	C	D	C	E

   Se o grafo estivesse representado na estrutura de dados do SGB, qual seria a ordem dos arcos em cada lista v–>arcs?

Implementação

A função abaixo recebe um grafo g e um vértice r e marca o território de r.  A pilha de vértices ativos é

ativo,  ativo–>próximo,  ativo–>próximo–>próximo,  . . . , r,  NULL.

(O fundo da pilha é sempre r.)  O conjunto A(v) é representado pelo utility field arcocorrente:  para cada vértice v,  v–>arcocorrente é o próximo arco, dentre os que saem de v, que deve ser examinado.

#define arcocorrente w.A 
#define próximo y.V

void busca_em_profundidade (Graph* g, Vertex* r) {
  Vertex* v, * w, * ativo; Arc* a;
  for (v = g–>vertices; v < g–>vertices+g–>n; v++) { 
     v–>marca = 0;
     v–>arcocorrente = v–>arcs;
  }
  r–>marca = 1;
  ativo = r;  ativo–>próximo = NULL;
  while (ativo != NULL) {
     v = ativo;
     a = v–>arcocorrente;
     if (a != NULL) {                     
        w = a–>tip;
        v–>arcocorrente = a–>next;
        if (w–>marca == 0) {
           w–>marca = 1;
           w–>próximo = ativo;     /* empilha w */
           ativo = w;
        }
     }
     else ativo = ativo–>próximo;  /* desempilha */
  }
}

Implementação com predecessores

A busca em profundidade fica melhor se escrita com predecessores no lugar das marcas, pois nesse caso os próprios predecessores podem representar a pilha de vértices ativos: a pilha fica sendo

v,  v–>pred,  v–>pred–>pred,  . . . ,  r.

Essa seqüência descreve, de trás-pra-diante, um caminho de r a v.

#define arcocorrente w.A 
#define pred x.V

void busca_em_profundidade (Graph* g, Vertex* r) {
  Vertex* v, * w; Arc* a;
  for (v = g–>vertices; v < g–>vertices+g–>n; v++) {
     v–>pred = NULL;
     v–>arcocorrente = v–>arcs;
  }
  v = r–>pred = r;
  while (1) {
     a = v–>arcocorrente;
     if (a != NULL) {               /* avança */
        w = a–>tip;
        v–>arcocorrente = a–>next;
        if (w–>pred == NULL) {
           w–>pred = v;             /* empilha w */
           v = w;
        }
     }
     else {                         /* volta */
        if (v == r)  break;
        v = v–>pred;                /* desempilha */
     }
  }
}

Um vértice v é considerado marcado se v–>pred for diferente de NULL.   Pequena variante: poderíamos trocar o while por

  while (r–>arcocorrente != NULL) {
     Arc* a = v–>arcocorrente;
     if (a != NULL) { 
        w = a–>tip;
        v–>arcocorrente = a–>next;
        if (w–>pred == NULL) {
           w–>pred = v;
           v = w;
        }
     }
     else  v = v–>pred;
  }

Exercícios

2. Onde está o erro nessa tentativa de implementacão da busca em profundidade?

   void errado (Graph* g, Vertex* r) {
     Vertex* v;
     for (v = g–>vertices; v < g–>vertices+g–>n; v++) {
        v–>pred = NULL;
        v–>arcocorrente = v–>arcs;
     }
     v = r;
     while (v != NULL) {
        Arc* a = v–>arcocorrente;
        if (a != NULL) { 
           Vertex* w = a–>tip;
           v–>arcocorrente = a–>next;
           if (w–>pred == NULL) {
              w–>pred = v;
              v = w;
           }
        }
        else  v = v–>pred;
     }
     r–>pred = r;
   }
   

3. Escreva uma variante da função busca_em_profundidade que receba um vértice  r  e imprima, uma e uma só vez, o nome de cada vértice do território de  r.

4. Escreva uma variante da função busca_em_profundidade que marque os vértices do terrítório de r com 1, 2, 3, etc. à medida que eles forem sendo encontrados.

Versão recursiva

A maneira mais cômoda de escrever o algoritmo de busca em profundidade é recursiva. A pilha de vértices ativos (e portanto o ponteiro arcocorrente) não aparece explicitamente: ela é criada e administrada pelo mecanismo de recursão.

#define pred x.V

void busca_em_profundidade_rec (Graph* g, Vertex* r) {
   Vertex* v;
   for (v = g–>vertices; v < g–>vertices+g–>n; v++) 
      v–>pred = NULL;
   r–>pred = r;
   dfs(r);
}

void dfs (Vertex* v) {
   Vertex* w; Arcs* a;
   for (a = v–>arcs; a != NULL; a = a–>next) {
      w = a–>tip;
      if (w–>pred == NULL) {
         w–>pred = v;
         dfs(w);
      }
   }
}