Structures de données et algorithmes · Graphes

Arbres couvrants de poids minimal

L'ensemble d'arêtes le moins coûteux qui connecte tous les sommets sans cycle.

Commencer une leçon sur Arbres couvrants de poids minimal

À apprendre d'abord

• Union-find: Une structure qui suit quels éléments appartiennent au même groupe et fusionne les groupes rapidement.
• Tas et files de priorité: Une structure en arbre qui garde toujours l'élément le plus petit, ou le plus grand, rapide à trouver.

Mène à

• Algorithmes gloutons: Faire le meilleur choix local à chaque étape en faisant confiance que cela mène à la meilleure réponse globale.

Notions liées

• Algorithme de Dijkstra: Trouver le chemin le moins coûteux d'un sommet vers tous les autres quand aucun poids d'arête n'est négatif.
• Algorithmes gloutons: Faire le meilleur choix local à chaque étape en faisant confiance que cela mène à la meilleure réponse globale.