Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Caminhos mínimos

(Esta página corresponde aproximadamente à seção 18.7 (Breadth-First Search), p.114-124, do capítulo 18 do livro de Sedgewick.)

Distância

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.

Exercícios

1. Seja s um vértice de digrafo G. Para cada vértice x do digrafo, seja dist(x) a distância de s a x em G.  Mostre que  dist(w) ≤ dist(v) + 1  para todo arco v-w.
2. Seja s um vértice de um digrafo G. Suponha que conhecemos a distância entre s e cada um dos demais vértices do digrafo. O que se pode dizer sobre a distância entre dois vértices quaisquer v e w?
3. Critique a seguinte função. Ela promete devolver a distância de s a t.

          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];
          }
   

Busca em largura e distâncias

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

• zero ou mais vértices à distância d de s,
• seguidos de zero ou mais vértices à distância d+1 de s,

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.

Exemplo

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 

Exercícios

4. Escreva uma versão da função DIGRAPHdist para digrafos representados por listas de adjacência.
5. A seguinte função promete calcular a distância de um vértice s a cada um dos demais vértices do grafo G.  A função está correta?

      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++;
         }
      }
   

6. Escreva uma função que receba um vértice  s  de um grafo  G  (representado por suas listas de adjacência) e armazene num vetor global  dist  as distâncias de  s  a cada um dos demais vértices.   Sua função não deve invocar outras funções.  Escreva código simples, sem variáveis supérfluas e sem comandos supérfluos.
7. Seja s um vértice de um grafo conexo G.  Suponha dado um vetor dist tal que dist[v] é a distância de s a v para cada vértice v.  Escreva uma função que receba um vértice w e imprima um caminho mínimo de w a s.

Caminhos mínimos e arborescência de distâncias

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)

Exercícios

8. Considere o grafo definido pelas arestas abaixo. Represente o grafo por uma matriz de adjacência.

   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.

9. Represente o grafo abaixo por listas de adjacência. Insira as arestas, na ordem dada, num grafo inicialmente vazio.

   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.

10. Escreva uma versão de DIGRAPHdist que calcule uma arborescência de distâncias. Escreva código simples e "enxuto", sem o vetor dist.

Desempenho

A função DIGRAPHdist é linear:  ela consome tempo proporcional a  V²  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.

Exercícios

11. Denote por dist(v,w) a distância entre dois vértices v e w num grafo conexo.  O diâmetro de um grafo conexo é a valor máximo da expressão  dist(v,w)  com v e w variando no conjunto de todos os vértices.  Escreva uma função que calcule o diâmetro de qualquer grafo conexo.