Алгоритм MST, выбирая минимальное ребро из каждой вершины?

Question

Можно ли создать MST, просто просматривая вершины графа и выбирая наименьшее ребро из этой вершины и принимая объединение всех этих ребер? Кажется, это не противоречит свойству cut и будет более эффективным, чем реализация алгоритма Prim.

Answer 1

Неа. Вершины могут иметь наименьшее ребро, поэтому вы не можете соединить их все:

A---1---B
|       |
2       2
|       |
C---1---D

Для создания MST вам нужен хотя бы один из ребер с весом 2, но ни один из них не является наименьшим ребром для любой вершины. .

Answer 2

Алгоритм Крускала для построения MST

1. Инициализация H = *.
2. Сортировка ребер в порядке возрастания весов.
3. L oop по ребрам в увеличение порядка весов.
   • Если конечные точки e не связаны в H.
     • Добавить e к H.

Источник: https://www.cc.gatech.edu/~rpeng/CS3510_F17/Notes/Sep27MST.pdf

Если вы просто итерируете по всем ребрам без учета, если они являются частью MST, то вы не можете быть уверены, что они не будут образовывать цикл.