Théorie des graphes : algo de Kruskal

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!

<a href="http://img503.imageshack.us/my.php?image=graphezi0.jpg" target="_blank"><img src="http://img503.imageshack.us/img503/9528/graphezi0.th.jpg" border="0" alt="Free Image Hosting at www.ImageShack.us" /></a>

Spartan

pour faire plus propre : http://img503.imageshack.us/my.php?image=graphezi0.jpg

Spartan

Si je comprend bien la différence c'est que suivre un chemin revient à ne pas faire demi-tour, contrairement au parcours de l'arbre...
Donc comme priorité tu créé un arc depuis une extrémité?!? Ne peut-on pas dire qu'un chemin est un arbre particulier? Donc tu résous ton pb avec un arbre et si ce n'est pas un chemin ( plus de 2 extrémités, boucles exluses), tu dois choisir de couper un arc au regroupement de branches.
Bon ca doit pas être très clair mais ton problème non plus...

Si je comprend bien la différence c'est que suivre un chemin revient à ne pas faire demi-tour, contrairement au parcours de l'arbre...
Donc comme priorité tu créé un arc depuis une extrémité?!? Ne peut-on pas dire qu'un chemin est un arbre particulier? Donc tu résous ton pb avec un arbre et si ce n'est pas un chemin ( plus de 2 extrémités, boucles exluses), tu dois choisir de couper un arc au regroupement de branches.

Bonjour à tous, je cherche une solution pour chercher un arbre dans un graphe, pouvez vous m'aider , c'est très urgent, j'ai un TP que je dois rendre le plus top possible.
merci.