plus petite somme du poids graphique, où chaque noeud sont connceted (comme un réseau)

Question

Quel algorithme je peux utiliser pour problème comme celui-ci:

utiliser un graphique positif pondéré, je veux savoir une plus petite somme possible de poids où chaque nœud est connecté (connecté comme un réseau, où chaque nœud est un périphérique réseau, par exemple).

Dans ce réseau, chaque nœud peut être connecté à un autre nœud par d'autres nœuds. Mais tous les nœuds du graphe d'entrée doivent être dans un réseau.

Quelqu'un peut-il m'aider?

Answer 1

Je crois que le réseau résultant que vous voulez est un arbre recouvrant minimum, qui a deux algorithmes bien connus: Kruskal's et Prim's.

Answer 2

Vous cherchez un arbre recouvrant minimum (MST).