En ce momentGenshin ImpactValhallaBreath of the wildAnimal CrossingGTA 5Red dead 2
Liste des sujets
algorithme de Kruskal
_Ciel_
Niveau 10
17 décembre 2011 à 20:57:07
Bonjour, quelqu'un pourrait m'expliquer le système de fusion de liste lorsque l'on programme l'algorithme de Kruskal ? en fait on range les arêtes dans l'ordre décroissant puis on ajoute successivement les arêtes en rejetant les arêtes qui forment un cycle avec celles déjà accepter. Mais j'ai pas compris dans le programme ce qui permet de rejeter ou d'accepter une arête supplémentaire ?
godrik
Niveau 30
17 décembre 2011 à 21:12:05
il faut utiliser une structure de donne de type disjoint set. Avec des techniques de type path compression ou representative.
