Discussão Geral

Professor, estudando o algoritmo de Prim para a prova e olhando de novo as implementações, fiquei com uma dúvida na implementação para grafos esparsos...

É no fim dessa parte do código:

      for (t = G->adj[v]; t != NULL; t = t->next) {
         w = t->v;
         if (st[w] != -1) continue;
         if (fr[w] == -1) { 
            wt[w] = t->wt; 
            PQinsert(w); 
         } 
         else if (t->wt < wt[w]) { 
            wt[w] = t->wt; 
            PQdec(w); 
         }
         fr[w] = v; 
      }

Pelo que entendi, cada iteração pega um vértice w da lista de v. Se w já está na árvore, avança. Se w não está na árvore e ainda não teve contato com vértices da árvore, o wt[w] recebe o valor t->wt e w é inserido na fila. Se w não está na árvore e já teve algum contato com a árvore, então é verificado se o peso que acaba de ser encontrado é menor do que o atualmente setado em wt[w]. Se for menor, wt[w] é atualizado e é chamado o PQdec.

Mas se o fr[w] = v está fora do "if-else", então ele sempre será aplicado, desde que w não esteja na árvore. Então o fr[w] é alterado mesmo que wt[w] não mude. Não é errado fazer essa atualização se o wt[w] não foi atualizado, ou seja, se o wt[w] é referente à aresta que liga w e algum outro vértice da árvore?

Deve ter alguma coisa que eu não estou percebendo...
Espero ter sido claro...