Imagine que seu grafo está representado por uma lista de adjacência de forma que os vértices em cada lista estão ordenados pelos peso das arestas. Como você pode modificar o algoritmo de Prim nesse caso para tirar proveito dessa organização?
53. Podemos afirmar que o caminho entre dois vértices de um grafo que faz parte da árvore geradora mínima é o caminho mais curto entre esses dois vértices?

Passo 1

O enunciado pede duas coisas: (1) dada uma lista de adjacência onde os vizinhos de cada vértice já vêm ordenados por peso, como adaptar o Prim para tirar proveito disso; (2) se o caminho entre dois vértices numa árvore geradora mínima (MST) é sempre o caminho de menor peso entre esses vértices no grafo original. Vamos usar conceitos de Prim e de comparação entre caminhos em grafos.

Passo 2

Na versão clássica de Prim usamos um min‐heap que armazena todas as arestas que cruzam do conjunto já incluído no MST (chamado de {\tt X}) para o conjunto fora dele (complemento de {\tt X}). Cada vez que incluímos um vértice novo, inserimos no heap todas as arestas incidentes nesse vértice que apontam para fora de {\tt X}. Com listas ordenadas, reduzir esse custo é fácil: em vez de empurrar todas as arestas, inserimos apenas a menor aresta ainda não considerada de cada lista.
Para isso, para cada vértice já em {\tt X} mantemos um ponteiro para a “próxima” aresta da sua lista de adjacência ordenada. Inicialmente, quando adicionamos um vértice u, avançamos no seu vetor até achar o primeiro vizinho vnotin X e então inserimos no heap o par (u,v) com o peso correspondente. Quando extraímos do heap a aresta (u,v) e incluímos v no MST, voltamos à lista de u, avançamos o ponteiro para a próxima aresta e, se existir outro wnotin X, inserimos (u,w) no heap.

Passo 3

Dessa forma cada aresta da lista de adjacência é examinada exatamente uma vez (avançamos o ponteiro uma vez por aresta) e o heap armazena no máximo uma aresta por vértice em {\tt X}. O custo fica em O(m + nlog n), aproveitando a ordenação prévia.

Passo 4

Sobre a segunda pergunta: não, o caminho entre dois vértices numa MST não é, em geral, o caminho mais curto no grafo original. Um contraexemplo simples é um triângulo a,b,c com pesos omega(a,b)=2, omega(b,c)=2 e omega(a,c)=3. A MST escolherá ab e bc, então o caminho ato c na árvore tem custo 4, mas existe a aresta direta de custo 3, mais barato do que 4.

Resposta

  1. Adaptação do Prim: use uma varredura “lazy” nas listas ordenadas, mantendo para cada vértice já inserido um ponteiro para sua próxima aresta não testada e insira no heap só essa aresta. Ao extrair uma aresta (u,v), inclua v e avance o ponteiro de u, inserindo a nova aresta fronteira. Isso inspeciona cada aresta só uma vez, em O(m + nlog n). 2) Não; o caminho entre dois vértices numa MST nem sempre é o mais curto no grafo original, como mostra o triângulo com pesos 2,2 e 3.

Exercícios relacionados