Algoritmos para Grafos, via Sedgewick | Índice remissivo
Um algoritmo de busca (ou varredura) é um algoritmo que examina, sistematicamente, todos os vértices e todos os arcos de um digrafo. Cada arco é examinado 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 de árvore em preordem, exploração de labirintos, fio de Ariadne (no mito de Teseu e o Minotauro), etc.
(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. Pode-se dizer que a função visita os vértices do digrafo "em ordem DFS". Cada vértice v recebe um rótulo (= label ) que dá o número de ordem do vértice. Os rótulos são armazenados num vetor lbl indexado pelos vértices. [Sedgewick escreve "pre" no lugar do meu "lbl", pois está pensando no algoritmo de varredura de arborescências conhecido como preorder traversal. Infelizmente, Sedgewick continua escrevendo "pre" em outros contextos, que não têm relação alguma com preorder.]
/* Vamos supor que nossos digrafos têm no máximo maxV vértices. */
#define maxV 10000 static int conta, lbl[maxV];/* A função DIGRAPHdfs visita todos os vértices e todos os arcos do digrafo G. A função registra a ordem em que os vértices são visitados atribuindo um número de ordem lbl[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++) lbl[v] = -1; for (v = 0; v < G->V; v++) if (lbl[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; lbl[v] = conta++; for (w = 0; w < G->V; w++) if (G->adj[v][w] != 0) if (lbl[w] == -1) dfsR(G, w); }
A função DIGRAPHdfs é apenas uma interface com o usuário. 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 abaixo é a versão de dfsR para digrafos representados por listas de adjacência. (Inspirado no programas 18.2, p.85, de Sedgewick.) */
void dfsR (Digraph G, Vertex v) { link p; lbl[v] = conta++; for (p = G->adj[v]; p != NULL; p = p->next) if (lbl[p->w] == -1) dfsR(G, p->w); }
Se lbl[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.
O exemplo abaixo ilustra uma busca em profundidade num grafo, ou seja, num digrafo simétrico. O grafo é definido pelo conjunto de arestas
0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5 .
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. A execução de cada nova instância de dfsR é indicada por uma indentação apropriada das linhas.
dfsR(G,0)
0-2 dfsR(G,2)
2-0
2-6 dfsR(G,6)
6-2
6-4 dfsR(G,4)
4-3 dfsR(G,3)
3-4
3-5 dfsR(G,5)
5-0
5-3
5-4
4-5
4-6
4-7 dfsR(G,7)
7-0
7-1 dfsR(G,1)
1-7
7-4
0-5
0-7
O vetor lbl terá a seguinte evolução (com "*" no lugar de "-1"):
0 1 2 3 4 5 6 7
---------------
0 * * * * * * *
0 * 1 * * * * *
0 * 1 * * * 2 *
0 * 1 * 3 * 2 *
0 * 1 4 3 * 2 *
0 * 1 4 3 5 2 *
0 * 1 4 3 5 2 6
0 7 1 4 3 5 2 6
Portanto, os vértices são visitados na ordem 0 2 6 4 3 5 7 1. (Esse exemplo foi copiado da figura 18.5, p.82, de Sedgewick.)
0-2 0-5 1-2 3-4 4-5 3-5
e exiba um "trace" 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 exiba um "trace" 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 exiba um "trace" 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 0-9 1-4 1-9 2-7 2-10 2-12 3-12 5-12 6-10 6-12 7-10 8-11
(figura 18.8, p.87, de Sedgewick). 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.)
A função DIGRAPHdfs combinada com a versão de dfsR para matriz de adjacência consome tempo proporcional a
V2.
(Isso é proporcional ao tempo necessário para ler a matriz de adjacência; o algoritmo é, portanto, muito rápido). Combinada com a versão de dfsR para listas de adjacência, a função DIGRAPHdfs consome tempo proporcional a
V+E.
(Isso é proporcional ao tempo necessário para ler todas as listas de adjacência; o algoritmo é, portanto, muito rápido).
0-1 0-2 1-3 1-4 1-5 3-6 3-7 4-7 5-7
Se as listas de adjacência do grafo fossem construídas de maneira apropriada, a numeração dos vértices dada abaixo poderia ser produzida por uma busca em profundidade?
v 0 1 2 3 4 5 6 7
lbl[v] 0 1 4 3 2 5 6 7
#include "STACK.h"
static int conta, lbl[maxV];
void DIGRAPHdfs? (Digraph G) {
Vertex v;
conta = 0;
for (v = 0; v < G->V; v++) lbl[v] = -1;
for (v = 0; v < G->V; v++)
if (lbl[v] == -1)
dfs?(G, v);
}
void dfs? (Digraph G, Vertex v) {
Vertex w;
STACKinit(G->A);
lbl[s] = conta++;
STACKpush(s);
while (!STACKempty()) {
v = STACKpop();
for (w = 0; w < G->V; w++)
if (G->adj[v][w] == 1)
if (lbl[w] == -1) {
lbl[w] = conta++;
STACKpush(w);
}
}
}