Algorithme kruskal
abdel
-
abdel -
abdel -
bonjour
je dois utiliser une matrice pour le probleme du voyageur
de commerce en java
j'aimerais implementer l'algorithme de kruskal mais je n'arrive pas a comprendre la condition pour choisir une arete la condition
qui est: qui ne forme pas de circuit j'arrive pas a l'implementer
en java
merci de votre aide
je dois utiliser une matrice pour le probleme du voyageur
de commerce en java
j'aimerais implementer l'algorithme de kruskal mais je n'arrive pas a comprendre la condition pour choisir une arete la condition
qui est: qui ne forme pas de circuit j'arrive pas a l'implementer
en java
merci de votre aide
Configuration: Windows XP Opera 9.00
1 réponse
-
voila l'algo:
KRUSKAL (G,w)
1 E := ø
2 pour chaque sommet v de G
3 faire CRÉER-ENSEMBLE (v)
4 trier les arêtes de G par ordre croissant de poids w
5 pour chaque arête (u,v) de G prise par ordre de poids croissant
6 faire si ENSEMBLE-REPRÉSENTATIF (u) ≠ ENSEMBLE-
REPRÉSENTATIF (v)
7 alors ajouter l'arête (u,v) à l'ensemble E
8 UNION (u,v)
9 retourner E
pourrias-tu me péciser où se trouve exactement ton problème.
merci
