Алгоритъмът на Крускал - Изграждане на оптимална рамка
В началото на XIX век геометърът от Берлин Якоб Щайнер си поставя задачата да свърже три села, така че дължината им да е най-къса. Впоследствие той обобщава този проблем: изисква се да се намери точка на равнината, така че разстоянието от нея до n други точки да е най-малкото. През 20-ти век работата по тази тема продължи. Решено е да се вземат няколко точки и да се свържат по такъв начин, че разстоянието между тях да е най-кратко. Всичко това е специален случай на изследвания проблем.
Алчни алгоритми
Алгоритъмът на Крускал принадлежи към алчните алгоритми (те също се наричат градиентни алгоритми). Същността на това е най-голямото изплащане на всяка стъпка. Не винаги алчните алгоритми дават най-доброто решение на проблема. Има теория, която показва, че когато се прилагат към конкретни проблеми, те осигуряват оптимално решение. Това е теорията на матроидите. Алгоритъмът на Крускал се отнася до такива проблеми.
Намиране на рамката с минимално тегло
Разглежданият алгоритъм изгражда оптимален скелет на графика. Проблемът за него е следният. Получава се неориентирана графика без множество ръбове и цикли, а на множеството от нейните ръбове се дава функция на тежестта w, която присвоява на всеки ръб e число - теглото на ръба - w (e). Теглото на всяко подмножество от множеството ръбове се определя от сумата от теглата на неговите ръбове. Необходимо е да се намери рамката с най-малкото тегло.
Алгоритъмът на Крускал работи по този начин. Първо, всички ръбове на оригиналната графика са подредени във възходящ ред на тежестите. Първоначално скелетът не съдържа никакви ръбове, но включва всички върхове на графиката. След следващата стъпка от алгоритъма, един ръб се добавя към вече изградената част на скелета, която е обхващаща гора. Не е случайно избран. Всички ръбове на графиката, които не принадлежат на каркаса, могат да се нарекат червени и зелени. Върховете на всеки червен ръб са в един свързан компонент на гората в процес на изграждане, а върховете на зеления ръб са в различни. Следователно, ако добавите червен ръб там, се появява цикъл и ако е зелен, компонентът за свързаност в гората, получен след тази стъпка, ще бъде с един по-малко. По този начин не може да се добави червен ръб към получената конструкция, но може да се добави всеки зелен ръб, за да се създаде гора. И се добавя зелен ръб с минимално тегло. Резултатът е най-лекият кадър.
Изпълнение
Ние обозначаваме текущата гора с F. Тя разделя множеството върхове на графиката на свързани региони (техният съюз образува F и те не се пресичат по двойки). Червените ръбове имат двата върха в една и съща част. Част (x) е функция, която за всеки връх x връща името на частта, към която принадлежи x. Unite (x, y) е процедура, която изгражда нов дял, състоящ се от обединението на x и y частите и всички останали части. Нека n е броят на ръбовете в графиката. Всички тези понятия са включени в алгоритъма на Крускал. Изпълнение: