Discussão:Algoritmo de Prim

Algumas sugestoes:

- O codigo em PHP da implementacao está enorme, não seria possivel torna-lo um pouco mais perceptível, optimizando-o?
- falta mostrar o pseudo-código. Mais importante que a implementação de um algoritmo, é descrevê-lo genericamente em pseudo-codigo.

80.172.69.100 (discussão) 16h43min de 11 de Maio de 2008 (UTC)

O código em PHP está com uma complexidade de tempo O(|V|³*|A|), ou seja, O(|V|^5) para um grafo completo. Muito além das complexidades O(|V|²+|A|) e O([|V|+|A|] log |V|) que se pode alcançar. Vou por um pseudocódigo e implementações em C, C++ e Python. Mas seria bom alguém otimizar essa em PHP. RafaelCLP (discussão) 17h14min de 25 de agosto de 2013 (UTC)

Desisti de por uma implementação em C/C++, pois achei a implementação em Python bem simples e fácil de entender, sendo desnecessário trazer a mesma implementação em outras linguagens. De qualquer forma, se alguém achar interessante, o algoritmo de Dijkstra é quase idêntico ao algoritmo de Prim, então fiquem à vontade para adaptar a minha implementação de Dijkstra para Prim. RafaelCLP (discussão) 07h24min de 27 de agosto de 2013 (UTC)