Théorie des graphes : algo de Kruskal

cs_thespartan Messages postés 36 Date d'inscription samedi 3 février 2007 Statut Membre Dernière intervention 26 mai 2008 - 16 mai 2007 à 01:39
cs_papillon2000 Messages postés 94 Date d'inscription dimanche 30 avril 2006 Statut Membre Dernière intervention 21 juin 2010 - 1 févr. 2010 à 16:15
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

Spartan

4 réponses

cs_thespartan Messages postés 36 Date d'inscription samedi 3 février 2007 Statut Membre Dernière intervention 26 mai 2008
16 mai 2007 à 01:40
HSylvio Messages postés 116 Date d'inscription jeudi 22 juillet 2004 Statut Membre Dernière intervention 14 juin 2012
8 juin 2007 à 15:00
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...
HSylvio Messages postés 116 Date d'inscription jeudi 22 juillet 2004 Statut Membre Dernière intervention 14 juin 2012
8 juin 2007 à 15:00
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.
cs_papillon2000 Messages postés 94 Date d'inscription dimanche 30 avril 2006 Statut Membre Dernière intervention 21 juin 2010
1 févr. 2010 à 16:15
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.
Rejoignez-nous