Quels algorithmes sont utilisés pour trouver une forêt couvrant au minimum?

Question

Comme Wikipedia dit:

forêt couvrante minimum est une union des arbres de recouvrement minimaux pour ses composants connectés.

Pour trouver minimum spanning tree on peut utiliser par exemple Prim's algorithm, Kruskal's algorithm ou Borůvka's algorithm.

Quel algorithme pouvons-nous utiliser pour trouver la forêt couvrant au minimum?

Answer 1

Je ne vois pas comment vous avez besoin d'un autre algorithme que celui que vous utilisez pour les arbres - vous devrez peut-être les adapter un peu.
Si vous utilisez par exemple l'algorithme de Kruskal, vous obtenez toutes les arêtes les moins chères dans chaque sous-graphe/arborescence minimale de votre forêt (maintenant aussi minimum). Ou vous pouvez utiliser l'algorithme de Prim et si votre itération s'arrête, redémarrez-le avec un nœud qui n'est pas encore connecté (c'est-à-dire avec un autre arbre). Donc, ma réponse en une phrase: "Les algorithmes utilisés pour trouver une forêt couvrant au minimum sont les mêmes que ceux qui sont utilisés pour trouver un arbre recouvrant minimum - dans certains cas avec des adaptations et dans certains cas sans les."