Este capítulo discute uma implementação clássica do algoritmo genérico de busca. Nessa implementação, o conjunto de vértices ativos é administrado como uma fila (= queue), ou seja, cada iteração escolhe o vértice ativo que foi marcado há mais tempo. O resultado dessa política é conhecido como busca em largura (= breadth-first search = BFS).
Dado que o conjunto de vértices ativos é tratado como uma fila, podemos lidar, de uma só vez, com todos os arcos que saem de v e assim dispensar o conjunto A(v). O algoritmo genérico de busca pode ser reformulado assim:
enquanto a fila não está vazia faça
seja v o primeiro vértice da fila
para cada vértice w adjacente a v faça
se w não está marcado
então marque w
então insira w no final da fila
retire v da fila
Eis a implementação do algoritmo em C, usando as estruturas de dados do SGB:
#define marca x.I
#define prox y.V
void busca_em_largura (Graph *g, Vertex *r) {
Vertex *v, *w, *ativo, *ultimo; Arc *a;
for (v = gvertices; v < gvertices + gn; v++)
vmarca = 0;
rmarca = 1;
ativo = ultimo = r; ultimoprox = NULL;
while (ativo ≠ NULL) {
v = ativo;
for (a = varcs; a ≠ NULL; a = anext) {
w = atip;
if (wmarca ≡ 0) {
wmarca = 1;
wprox = NULL;
ultimoprox = w;
ultimo = w;
}
}
ativo = ativoprox;
}
}
A função recebe um grafo g e um vértice r e marca o território de r. Um vértice v é considerado marcado se vmarca vale 1. A fila de vértices ativos é
ativo, ativoprox, ativoproxprox, .… , ultimo, NULL.
É fácil escrever uma versão com predecessores no lugar das marcas:
#define pred x.V
#define prox y.V
void busca_em_largura (Graph *g, Vertex *r) {
Vertex *v, *w, *ativo, *ultimo; Arc *a;
for (v = gvertices; v < gvertices + gn; v++)
vpred = NULL;
rpred = r;
ativo = ultimo = r; ultimoprox = NULL;
while (ativo ≠ NULL) {
v = ativo;
for (a = varcs; a ≠ NULL; a = anext) {
w = atip;
if (wpred ≡ NULL) {
wpred = v;
wprox = NULL;
ultimoprox = w;
ultimo = w;
}
}
ativo = ativoprox;
}
}
ativo = ativoproxlogo depois da linha
v = ativono código da função busca_em_largura?
derrubeo código.
for (v = gvertices; v < gvertices + gn; v++)
vmarca = 0, vprox = NULL;
ativo = ultimo = r;
while (ativo ≠ NULL) {
v = ativo;
vmarca = 1;
for (a = varcs; a ≠ NULL; a = anext) {
w = atip;
if (wmarca ≡ 0) {
ultimoprox = w;
ultimo = w; } }
ativo = ativoprox; }
#define marca x.I
#define prox y.V
void busca (Graph *g, Vertex *r) {
Vertex *v, *w, *ativo; Arc *a;
for (v = gvertices; v < gvertices + gn; v++)
vmarca = 0;
rmarca = 1;
ativo = r; ativoprox = NULL;
while (ativo ≠ NULL) {
v = ativo;
ativo = ativoprox; /* 9 */
for (a = varcs; a ≠ NULL; a = anext) {
w = atip;
if (wmarca ≡ 0) {
wmarca = 1;
wprox = ativo;
ativo = w;
}
} /* 17 */
} /* 18 */
}
A função marca corretamente o território de r? O conjunto de vértices ativos parece ser administrado como uma pilha; isso é de fato verdade? Que acontece se a linha 9 for colocada entre as linhas 17 e 18?