Discussion :

[amateurc]

Bonjour,
je dois implémenter l'algo de prim de façon à ce qu'il soit le plus rapide possible, j'en suis arrivé à la conclusion qu'il me faut utiliser une file de priorité mais j'hésite entre deux : tas de Fibonacci et tas binomial. ma question est : lequel est le plus adapté au problème (en sachant que je dois le faire en C++) ?

je pencherai pour le tas binomial qui est apparemment le plus simple à implémenter(moins de pointeur ).

[PRomu@ld]

Si tu cherches le plus simple à implémenter, c'est sans doute le tas binomial.

Si tu cherches la performance, avec un tas de Fibonacci la complexité est plus faible.

La complexité avec le tas binomial (si je ne me plante pas trop ...) :

- O( V log( V ) + E log( V ) )

Avec un tas de Fibonacci :

- O( V log( V ) + E )

[amateurc]

d'accord merci pour la confirmation