Алгоритм Прима и несвязный граф

Question

Предположим, мы пытаемся применить алгоритм Прима к несвязному графу. Предположим, что этот несвязный граф имеет вершины a, b, c и d, где это d несвязно. Теперь мне нужно проверить свое понимание, если мы применим закон Прима к этому несвязному графу, алгоритм не достигнет вершины d и, следовательно, вернет MST только с вершинами a, band c. Так это правильно?

Answer 1

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

Минимальное связующее дерево (MST) или минимальное весовое остовное дерево является подмножеством ребер связанного , взвешенного по ребру неориентированный граф, который соединяет все вершины вместе, без каких-либо циклов и с минимально возможным общим весом ребра.