Algoritmos para Grafos, via Sedgewick | Índice remissivo
Um algoritmo de busca (ou varredura) é um algoritmo que visita, sistematicamente, todos os vértices e todos os arcos de um digrafo. Cada arco é visitado uma e uma só vez. Depois de visitar a ponta inicial de um arco, o algoritmo percorre o arco e visita sua ponta final.
Há muitas maneiras de fazer uma tal busca. Cada estratégia de busca é caracterizada pela ordem em que os vértices são visitados. Diremos que o k-ésimo vértice visitado durante a busca tem número de ordem k−1 .
Esta página introduz uma poderosa estratégia de busca conhecida como busca em profundidade (= depth-first search = DFS). A busca em profundidade, ou busca DFS, está relacionada com conceitos como backtracking, varredura em pré-ordem, exploração de labirintos, exploração Tremaux, fio de Ariadne (no mito de Teseu e o Minotauro), etc. A página Procurando caminhos já fez uma introdução à busca DFS.
[Esta página corresponde aproximadamente às seções 18.1 (Exploring a Maze) e 18.2 (Depth-First Search) do capítulo 18 (Graph Search) do livro de Sedgewick.]
A função DIGRAPHdfs abaixo executa uma busca em profundidade em um digrafo G. Dizemos que a função visita os vértices do digrafo "em ordem DFS" ou, mais precisamente, em pré-ordem (= preorder). Cada vértice v recebe um rótulo que dá o número de ordem do vértice. Os rótulos são armazenados num vetor pre indexado pelos vértices.
/* Vamos supor que nossos digrafos têm no máximo maxV vértices. */
static int conta, pre[maxV];/* A função DIGRAPHdfs visita todos os vértices e todos os arcos do digrafo G. A função atribui um número de ordem pre[x] a cada vértice x: o k-ésimo vértice visitado recebe número de ordem k-1. (Código inspirado no programa 18.3, p.87, de Sedgewick.) */
void DIGRAPHdfs( Digraph G) { Vertex v; conta = 0; for (v = 0; v < G->V; v++) pre[v] = -1; for (v = 0; v < G->V; v++) if (pre[v] == -1) dfsR( G, v); }/* A função dfsR supõe que o digrafo G é representado por uma matriz de adjacência. (Inspirado no programas 18.1, p.82, de Sedgewick.) */
void dfsR( Digraph G, Vertex v) { Vertex w; pre[v] = conta++; for (w = 0; w < G->V; w++) if (G->adj[v][w] != 0 && pre[w] == -1) dfsR( G, w); }
A função DIGRAPHdfs é apenas uma interface. A busca em profundidade propriamente dita é realizada pela função recursiva dfsR. A versão acima supõe que o digrafo está representado por sua matriz de adjacência, enquanto a versão abaixo supõe representação por listas de adjacência.
/* A função dfsR supõe que o digrafo G é representado por listas de adjacência. (Inspirado no programas 18.2, p.85, de Sedgewick.) */
void dfsR( Digraph G, Vertex v) { link p; pre[v] = conta++; for (p = G->adj[v]; p != NULL; p = p->next) if (pre[p->w] == -1) dfsR( G, p->w); }
A ordem em que os vértices são visitados (e portanto o conteúdo do vetor de rótulos pre) depende não só do digrafo mas também da ordem em que os vizinhos de cada vértice aparecem nas listas de adjacência.
Se pre[v] vale -1, dizemos que o vértice v ainda não foi visitado. Dizemos que um arco v-w foi visitado quando a função dfsR se depara com w ao examinar os vizinhos de v.
Qual a diferença entre a função DIGRAPHdfs de busca em profundidade e a função DIGRAPHpath de busca de caminhos? Há apenas duas pequenas diferenças: (1) DIGRAPHdfs visita todos os vértices do digrafo, enquando DIGRAPHpath visita apenas os que são acessíveis a partir de um vértice s e (2) DIGRAPHdfs numera os vértices na ordem em que eles são visitados, enquanto DIGRAPHpath marca todos os vértices que visita com um mesmo rótulo 1.
Considere o digrafo G definido pelos arcos 2-0 2-3 2-4 0-1 0-4 3-4 3-5 4-1 4-5 5-1 . Eis a matriz de adjacência do digrafo (com "-" no lugar de "0"):
- 1 - - 1 -
- - - - - -
1 - - 1 1 -
- - - - 1 1
- 1 - - - 1
- 1 - - - -
Segue o rastramento de DIGRAPHdfs(G). Cada linha da figura registra o momento em que um arco é visitado; registra também cada invocação de dfsR. A execução de cada nova instância de dfsR é indicada por uma indentação apropriada das linhas.
0 1 2 3 4 5
dfsR(G,0) 0 - - - - -
0-1 dfsR(G,1) 0 1 - - - -
0-4 dfsR(G,4) 0 1 - - 2 -
4-1
4-5 dfsR(G,5) 0 1 - - 2 3
5-1
dfsR(G,2) 0 1 4 - 2 3
2-0
2-3 dfsR(G,3) 0 1 4 5 2 3
3-4
3-5
2-4
Em cada linha da coluna direita da figura aparece o estado do vetor pre (com "-" no lugar de "-1") imediatamente depois da execução de "pre[v] = conta++" na correspondente invocação de dfsR. O estado final de pre informa que os vértice são visitados na ordem 0 1 4 5 2 3. Esta é, portanto, enumeração dos vértices em pré-ordem.
O exemplo abaixo ilustra uma busca em profundidade num grafo, ou seja, num digrafo simétrico. O grafo é definido pelo conjunto de arestas a seguir.
0-2 0-5 0-7 1-7 2-6 3-4 3-5 4-5 4-6 4-7
[Esse exemplo foi copiado da figura 18.5, p.82, de Sedgewick.]
Suponha que o grafo é representado por sua matriz de adjacência. A figura abaixo registra cada arco no momento em que ele é visitado e registra cada invocação de dfsR.
0 1 2 3 4 5 6 7
dfsR(G,0) 0 - - - - - - -
0-2 dfsR(G,2) 0 - 1 - - - - -
2-0
2-6 dfsR(G,6) 0 - 1 - - - 2 -
6-2
6-4 dfsR(G,4) 0 - 1 - 3 - 2 -
4-3 dfsR(G,3) 0 - 1 4 3 - 2 -
3-4
3-5 dfsR(G,5) 0 - 1 4 3 5 2 -
5-0
5-3
5-4
4-5
4-6
4-7 dfsR(G,7) 0 - 1 4 3 5 2 6
7-0
7-1 dfsR(G,1) 0 7 1 4 3 5 2 6
1-7
7-4
0-5
0-7
Os sucessivos estados do vetor de rótulos pre aparecem do lado direito da figura (com "-" no lugar de "-1"). O estado final de pre informa que os vértice são visitados na ordem 0 2 6 4 3 5 7 1.
0-2 0-5 1-2 3-4 4-5 3-5
e exiba o rastreamento da execução da função no formato do exemplo acima.
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
e faça o rastreamento da execução da função. Use o formato do exemplo acima.
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
e faça o rastreamento da execução da função. Suponha que as listas de adjacência são construídas inserindo os arcos acima, na ordem dada, num grafo inicialmente vazio. Use o formato do exemplo acima.
0: 1 4
1: 2 5
2: 3
3: 7
4: 8
5: 4
6: 5 10 2
7: 11 6
8: 9
9: 5 8
10: 9
11: 10
A função DIGRAPHdfs, combinada com a versão de dfsR para matriz de adjacência, consome tempo proporcional a
V2
quando aplicada a um digrafo com V vértices. (Isso é proporcional ao tempo necessário para ler a matriz de adjacência; o algoritmo é, portanto, muito rápido quando aplicado a um digrafo denso.)
Combinada com a versão de dfsR para listas de adjacência, a função DIGRAPHdfs consome tempo proporcional a
V + A
quando aplicada a um digrafo com V vértices e A arcos. (Isso é proporcional ao tempo necessário para ler todas as listas de adjacência.) Se o digrafo é esparso, esta segunda versão é mais rápida que a primeira.
Depois da execução da busca em profundidade, a sequência de números pre[0], pre[1], …, pre[V-1] é uma permutação de 0, 1, …, V-1, sendo V o número de vértices de G. Assim, para imprimir os vértices em pré-ordem basta inverter o vetor pre:
Vertex preordem[maxV];
int i;
for (v = 0; v < G->V; ++v)
preordem[pre[v]] = v;
for (i = 0; i < G->V; ++i)
printf( "%d ", preordem[i]);
0-1 0-2 1-3 1-4 1-5 3-6 3-7 4-7 5-7
Suponha que uma busca em profundidade visita os vértices na seguinte ordem: 0 1 5 7 4 3 6 2. Em que os ordem aparecem os vizinhos de cada vértice nas listas de adjacência?
0-1 0-9 1-4 1-9 2-7 2-10 2-12 3-12 5-12 6-10 6-12 7-10 8-11
Quantas dessas permutações coincidem com a ordem em que os vértices do grafo poderiam ser visitados pela função DIGRAPHdfs se usarmos a versão da função dfsR para listas de adjacência? (Sugestão: Considere todas as ordens em que os vértices podem aparecer nas listas de adjacência.)
#include "STACK.h"
static int conta, pre[maxV];
void DIGRAPHdfs?( Digraph G) {
Vertex v;
conta = 0;
for (v = 0; v < G->V; v++) pre[v] = -1;
for (v = 0; v < G->V; v++)
if (pre[v] == -1)
dfs?( G, v);
}
void dfs?( Digraph G, Vertex v) {
Vertex w;
STACKinit( G->A);
pre[s] = conta++;
STACKpush( s);
while (!STACKempty( )) {
v = STACKpop( );
for (w = 0; w < G->V; w++)
if (G->adj[v][w] == 1)
if (pre[w] == -1) {
pre[w] = conta++;
STACKpush( w);
}
}
}
Resposta: Sim, está certo. Mas se A for bem menor que V2 (é o que acontece com digrafos esparsos) então V+A é bem menor que V2.
Resposta: É verdade que muitas vezes lidamos com digrafos fracamente conexos, nos quais A ≥ V+1. Mas nem todos os digrafos são fracamente conexos, e portanto A pode até ser nulo!
