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?
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 , avançamos no seu vetor até achar o primeiro vizinho
e então inserimos no heap o par
com o peso correspondente. Quando extraímos do heap a aresta
e incluímos
no MST, voltamos à lista de
, avançamos o ponteiro para a próxima aresta e, se existir outro
, inserimos
no heap.
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
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
, 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
com pesos
,
e
. A MST escolherá
e
, então o caminho
na árvore tem custo
, mas existe a aresta direta de custo
, mais barato do que
.
Resposta
- 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
, inclua e avance o ponteiro de , inserindo a nova aresta fronteira. Isso inspeciona cada aresta só uma vez, em . 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.