Говорят, что алгоритм Kruskal для построения MST является жадным, но алгоритм выбирает глобальный минимум и вместо локального минимума в отличие от алгоритма Прима. Может кто-нибудь объяснить, как алгоритм Крускаля считается жадным?Как алгоритм Крускаля жадный?
Что мы делаем в Крускале? Сначала отсортируйте края по их весу. Тогда мы выберем это ребро, имеющее минимальный вес. Мы добавляем это ребро, если оно не делает циклов. Таким образом, мы идем вперед жадно. Так что это жадный подход. :)
Жадный подход называется жадным, потому что он принимает оптимальный выбор на каждом этапе ожидания, что даст полное оптимальное решение.
Это жадный алгоритм, потому что вы выбрали объединение двух наборов вершин на каждом шаге в соответствии с минимальным весом, вы выбрали край, который выглядит оптимальным на данный момент. Это жадный шаг, и, следовательно, алгоритм считается жадным.
в псевдокоде из википедии (прилагается), жадный шаг - по выбору (u,v), который является самым низким взвешенным краем, который соединяет два несвязанных компонента.
KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3 MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5 if FIND-SET(u) ≠ FIND-SET(v):
6 A = A ∪ {(u, v)}
7 UNION(u, v)
8 return A