Discussion :

[AlKoLiK]

Bonjour j'ai implémenté l'agorithme de kruskal qui sert à la recherche d'arbre recouvrant de poids minimal (arpm) dans un graphe pondéré seulement voilà, l'algo n'est pas parfait : il peut générer un chemin plutôt qu'un arbre dans certains cas. On m'a dit que la plupart des algos trouvés sur le net ne faisaient pas cette différence et mon prof m'a conseille d'utiliser des listes de priorités mais je ne vois pas comment faire... l'explication en image pour la subtile diffénrence arbre/chemin. Je peux donner des précisions sur mon problème si nécessaire. Merci!

http://img503.imageshack.us/my.php?image=graphezi0.jpg

[fumidu]

Un chemin est un cas particulier d'arbre. Dire qu'un chemin n'est pas un arbre, c'est comme dire qu'un carré n'est pas un rectangle il me semble.

J'ai l'impression que ce que tu veux, ce n'est pas l'arbre couvrant de poids minimum, mais un arbre couvrant de profondeur minimum. Et parmi les arbres couvrants de profondeur minimum, tu veux celui de poids minimum. Je me trompe ?

[PRomu@ld]

L'algorithme ne fait exactement que ce que tu lui demandes, il te trouve l'arbre couvrant de poids minimum, si la pondération de ton arbre change l'arbre couvrant pourra changer.

[FrancisSourd]

L'arbre couvrant de coût minimum peut effectivement être un chemin puisqu'un chemin est un arbre particulier.

Est que ton problème est de trouver l'arbre couvrant de coût minimum qui ne soit pas un chemin?