Проверяет ли алгоритм Prim связность графа самостоятельно?

Question

У меня есть несколько вопросов.

1. Нужно ли проверять связность графа перед передачей его в алгоритм Prim или алгоритм может позаботиться об этом?

Правильно ли работает алгоритм Прима на весах отрицательных ребер?

Как я могу использовать алгоритм Прима, чтобы найти остовное дерево без весов по его краям?

Answer 1

1.) Я считаю, что цель алгоритма Прима состоит в том, чтобы «сгенерировать» минимальное связующее дерево с узлами, которые вы ему даете.Я полагаю, вам нужно убедиться, что существует ребро между любыми двумя узлами, которые вы ему даете

2.) Алгоритм Прима (и алгоритмы минимального связующего дерева) должен корректно работать с весами отрицательных ребер

3.) Я так не думаю.Я полагаю, что вы могли бы сделать их все «1» или что-то еще, но я не думаю, что это привело бы к очень значимому минимальному остовному дереву.