Algoritmos para Grafos, via Sedgewick | Índice remissivo
(Esta página corresponde aproximadamente à seção 18.7 (Breadth-First Search), p.114-124, do capítulo 18 do livro de Sedgewick.)
Um caminho C num digrafo é mínimo se não existe outro caminho com mesma origem e mesmo término que C mas comprimento menor que o de C. É claro que todo caminho mínimo é simples.
A distância de um vértice s a um vértice t num digrafo é o comprimento de um caminho mínimo de s a t. Se não existe caminho algum de s a t, a distância de s a t é infinita. A distância de s a t é d se e somente se (1) existe um caminho de comprimento d de s a t e (2) nenhum caminho de s a t tem comprimento menor que d.
Em geral, a distância de um vértice s a um vértice t é diferente da distância de t a s. Num grafo, entretanto, as duas distâncias são iguais.
int distancia (Digraph G, Vertex s, Vertex t) {
int dist[1000], d;
Vertex v, w;
for (v = 0; v < G->V; v++) dist[v] = -1;
dist[r] = 0;
for (d = 0; d < G->V; d++)
for (v = 0; v < G->V; v++)
if (dist[v] == d)
for (w = 0; w < G->V; w++)
if (G->adj[v][w] == 1 && dist[w] == -1)
dist[w] = d + 1;
return dist[s];
}
O algoritmo de busca em largura foi concebido sob medida para calcular distâncias a partir de um vértice s. Ele visita todos os vértices que estão à distância 1 de s, depois todos os vértices que estão à distância 2 de s, e assim por diante.
static int dist[maxV];/* A função DIGRAPHdist armazena no vetor dist a distância do vértice s a cada um dos demais vértices do digrafo G: dist[v] é a distância de s a v. Distância infinita é representada por -1. (Código inspirado no programa 18.9, p.119, de Sedgewick.) */
void DIGRAPHdist (Digraph G, Vertex s) { Vertex v, w; for (v = 0; v < G->V; v++) dist[v] = -1; QUEUEinit(G->V); dist[s] = 0; QUEUEput(s); while (!QUEUEempty()) { v = QUEUEget(); for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1) if (dist[w] == -1) { dist[w] = dist[v] + 1; QUEUEput(w); } } }
No início de cada iteração (imediatamente da invocação de QUEUEempty), a fila consiste em
para algum d. Essa propriedade permite concluir que, no início de cada iteração, para todo vértice x, se dist[x] é diferente de -1 então dist[x] é a distância de s a x.
Considere o grafo (digrafo simétrico) definido pelo conjunto de arestas abaixo. (Trata-se do mesmo exemplo que examinamos na página de busca em largura.) Represente o grafo por sua matriz de adjacência.
0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5
Agora use a função DIGRAPHdist para calcular as distâncias a partir do vértice 0. Eis o estado do vetor dist no início de sucessivas iterações (com "*" no lugar de "-1"):
0 1 2 3 4 5 6 7
---------------
0 * * * * * * *
0 * 1 * * 1 * 1
0 * 1 * * 1 2 1
0 * 1 2 2 1 2 1
0 2 1 2 2 1 2 1
static int conta, dist[maxV];
void distance (Graph G, Vertex s) {
Vertex v, w;
conta = 0;
for (v = 0; v < G->V; v++) dist[v] = -1;
QUEUEinit(G->V);
dist[s] = 0;
QUEUEput(s);
while (!QUEUEempty()) {
v = QUEUEget();
for (w = 0; w < G->V; w++)
if (G->adj[v][w] == 1 && dist[w] == -1) {
dist[w] = conta;
QUEUEput(w);
}
conta++;
}
}
Se acrescentar ao código de DIGRAPHdist o cálculo de um vetor de pais parent, teremos uma representação da arborescência de busca em largura. No presente contexto, essa árvore pode ser chamada arborescência das distâncias: para cada vértice x tal que dist[x] é diferente de -1, o único caminho de s a x na arborescência é um caminho mínimo no digrafo. O fragmento de código abaixo imprime o inverso desse caminho:
for (v = x; v != s; v = parent[v])
printf("%d-", v)
printf("%d\n", s)
8-9 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
Calcule a distância do vértice 0 a cada um dos demais vértices. Faça um desenho da arborescência de distâncias.
8-9 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 .
Calcule a distância do vértice 0 a cada um dos demais vértices. Faça um desenho da arborescência de distâncias.
A função DIGRAPHdist é linear: ela consome tempo proporcional a V2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.
A versão de DIGRAPHdist que calcula a arborescência de distâncias também é linear.