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 de busca pode então ser reescrito assim:
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
| ponta inicial | 6 | 6 | 1 | 2 | 5 | 1 | 4 | 1 |
| arco | a | b | c | d | e | f | g | h |
| ponta final | 1 | 4 | 2 | 5 | 3 | 4 | 3 | 5 |
Se o grafo estivesse representado na estrutura de dados do SGB, qual seria a ordem dos arcos em cada lista varcs?
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, ativoprox, ativoproxprox, … , r.
O fundo da pilha é sempre r. O conjunto A(v) é representado pelo utility field arcocorrente: para cada vértice v, varcocorrente é o próximo arco, dentre os que saem de v, que deve ser examinado.
#define arcocorrente w.A
#define prox y.V
void busca_em_profundidade (Graph *g, Vertex *r) {
Vertex *v, *w, *ativo; Arc *a;
for (v = gvertices; v < gvertices + gn; v++) {
vmarca = 0;
varcocorrente = varcs;
}
rmarca = 1;
ativo = r; ativoprox = NULL;
while (ativo ≠ NULL) {
v = ativo;
a = varcocorrente;
if (a ≠ NULL) {
w = atip;
varcocorrente = anext;
if (wmarca ≡ 0) {
wmarca = 1;
wprox = ativo; /* empilha w */
ativo = w;
}
}
else ativo = ativoprox; /* desempilha */
}
}
A busca em profundidade fica melhor se escrita com predecessores no lugar das marcas. Os predecessores são representados por um campo pred e um vértice v é considerado marcado se vpred for diferente de NULL. Ademais, os próprios predecessores podem representar a pilha de vértices ativos: a pilha é
v, vpred, vpredpred, … , r.
Essa sequê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 = gvertices; v < gvertices + gn; v++) {
vpred = NULL;
varcocorrente = varcs;
}
v = rpred = r;
while (1) {
a = varcocorrente;
if (a ≠ NULL) { /* avança */
w = atip;
varcocorrente = anext;
if (wpred ≡ NULL) {
wpred = v; /* empilha w */
v = w;
}
}
else { /* volta */
if (v ≡ r) break;
v = vpred; /* desempilha */
}
}
}
O código fica ligeiramente mais simples
se trocarmos o while (1)
por
while (rarcocorrente
≠ NULL)
(isso mesmo: r
e não v
):
while (rarcocorrente ≠ NULL) {
a = varcocorrente;
if (a ≠ NULL) {
w = atip;
varcocorrente = anext;
if (wpred ≡ NULL) {
wpred = v;
v = w;
}
}
else v = vpred;
}
void errado (Graph *g, Vertex *r) {
Vertex *v;
for (v = gvertices; v < gvertices + gn; v++) {
vpred = NULL;
varcocorrente = varcs; }
v = r;
while (v ≠ NULL) {
Arc *a = varcocorrente;
if (a ≠ NULL) {
Vertex *w = atip;
varcocorrente = anext;
if (wpred ≡ NULL) {
wpred = v;
v = w; } }
else v = vpred; }
rpred = r; }
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 = gvertices; v < gvertices + gn; v++)
vpred = NULL;
rpred = r;
dfs (r);
}
void dfs (Vertex *v) {
Vertex *w; Arcs *a;
for (a = varcs; a ≠ NULL; a = anext) {
w = atip;
if (wpred ≡ NULL) {
wpred = v;
dfs (w);
}
}
}