Наименьшая сумма веса графа, где каждый узел связан (например, сеть)

Question

Какой алгоритм я могу использовать для такой задачи:

Иметь положительный взвешенный график, я хочу знать наименьшее возможная сумма весов, где каждый узел подключен (подключен как сеть, где каждый узел является, например, сетевым устройством).

В этой сети каждый узел может быть связан с другим узлом некоторыми другими узлами в пути. Но все узлы входного графа должны быть в сети.

Answer 1

Я полагаю, что полученная в результате сеть - это минимальное связующее дерево, которое имеет два хорошо известных алгоритма: Крускала и Прима .

Answer 2

Вы ищете минимальное связующее дерево (MST).