Algoritmo Prim - Ajuda

Como grafos é um assunto que de certa forma me interessa, vejamos se consigo te ajudar.

A explicação aqui parece aceitável: http://en.wikipedia.org/wiki/Prim%27s_algorithm (em inglês).

O vídeo aqui também é bem instrutivo: http://www.youtube.com/watch?v=BtGuZ-rrUeY. Há vários outros, não vi todos.

No vídeo que postei, há um resumo no final que pode te auxiliar. A tradução/adaptação é mais ou menos essa:

1 - escolha qualquer vértice para testar iniciar; verifique qual aresta conectada a este vértice tem o menor peso e adicione este peso à árvore;

2 - verifique todas as arestas conectadas ao vértice conectado à aresta selecionada no passo anterior e selecione a que tem menor peso;

3 - repita o passo 2 até que todos os vértices tenham sido acessados.

Importante notar que a complexidade do algoritmo é O(n^2), podendo ser melhorada com estruturas adequadas.

Curiosidade: tivemos uma vez que optar por implementar este algoritmo ou o de Kruskal. Optamos por Kruskal, mas simplesmente porque, para a aplicação em questão, o de Kruskal teria de ser executado apenas uma vez (ele dá o custo mínimo para todos os vértices), enquanto que o de Prim dá o custo mínimo apenas para o vértice inicial.

Abraço.

Obrigado! Semana que vem tenho uma prova que cai desde notação O(e tudo que envolve, contagem etc.), passando por árvores, até grafos. Acho que estou mais fraco em Notação O (por incrível que pareça,kkk). Então, tu tens algum material bem fácil de entender “Big O Notation” ? Se quiser você mesmo me explicar de maneira simplificada, agradeço. Eu preciso bater o olho em um método e já ter uma estimativa da notação, ainda tenho que trabalhar para chegar nesse nível, pelo menos nos códigos de maior complexidade.

O material pode ser em inglês, no problem. Estou estudando FULL-TIME essa semana e a próxima (final de semestre ).

Thanks

Vou ter que admitir que, apesar de ter estudado complexidade de algoritmos, meu conhecimento desse tema é escasso (não fui um grande estudante dessa disciplina, admito).

Passar o olho em um método/função e já saber a complexidade é algo meio difícil eu acho, ainda mais que alguns algoritmos possuem “armadilhas”, fazendo você pensar uma coisa e ser outra. Mas você acaba reparando algumas coisas (algumas das quais, creio que você já sabe):

• a complexidade geralmente está associada à operações repetitivas (loops e recursões). Nem vale muito a pena se preocupar com constantes, a não ser que seja solicitado;
• laços for e while são geralmente o jeito mais fácil de se chegar à complexidade. Leve em consideração quando e onde eles ocorrem (um for dentro de outro é um grande indicativo de uma possível complexidade n^2, por exemplo);
• repare nas condições e critérios de parada, pois em muitos casos elas cortam (dividem) o tempo de execução por uma determinada constante (n/2, por exemplo);
• métodos recursivos e de divisão e conquista (como o QuickSort) tendem a ter complexidade log, mas isso não é regra;

Leia aqui: http://en.wikipedia.org/wiki/Big_O_notation . Não é o melhor link do mundo, mas li por cima e creio que como base. O livro do Cormen (http://www.americanas.com.br/produto/187685/livros/informatica/informatica/livro-algoritmos-teoria-e-pratica) tem um bom contedúdo sobre isso (logo nos primeiros capítulos, se não me engano), embora seja um tanto pesado (em conteúdo e em gramas também). Se você tiver acesso, acho que vale a pena ver se você consegue digeri-lo.

Abraço.

Obrigado, cara! O Cormen é o livro base da disciplina, o problema que ele é meio “indigesto” para leigos, tem um abordagem mais matemática.

Mas de qualquer maneira, obrigado!