Цел: Да се намери най-тежкото (или най-лекото) покриващо дърво за неориентиран граф G с N върха и M ребра със зададени тегла.

Идея на алгоритъма:

1. Ребрата се прочитат и сортират по тегло.

2. Тръгваме от празна покриваща гора (гора състояща се от всички върхове на графа, без нито едно ребро).

3. Прибавяме ребра от сортирания масив по правилото:

• Aко реброто свързва върхове от едно дърво в гората, не го разглеждаме (отхвърляме го).
• Иначе добавяме реброто и обединяваме двете дървета, които реброто свързва.
• Когато броят на ребрата в гората стане N-1, гората съдържа единствено дърво, което е и решение на задачата.

Забележки:

1. Не се проверява коректност на данните.
2. G трябва да е свързан, иначе няма да се достигне бройката N-1 ребра в гората.

Бързодействие:

Първата фаза има сложност O(ln(M)*M), ако се ползва бърза сортировка (конкретната програма, дадена тук ползва бавна сортировка).

Втората фаза има сложност O(N^2).

Тъй като M<=N^2, общата сложност е ограничена от O(lnN*N^2).

Сходни задачи и допълнителни свойства:

• Да допуснем, че намираме най-тежкото дърво и че тежестта на ребрата има смисъл на пропускна способност (ширина) на пътищата между върховете.
  Полученото от алгоритъма дърво има следното допълнително свойство:
  За всеки два върха от графа да построим маршрута, ползващ само ребра от максималното дърво.
  Този маршрут е най-широкият възможен, т.е. най-лекото ребро от маршрута е по-тежко или равно на най-лекото ребро от всеки друг маршрут, свързващ същите върхове.

  Ако след greedy приложим treepath, ще решим задачата за намиране на най-широк път.

• Да допуснем, че намираме най-лекото дърво и че тежестта на ребрата има смисъл на разстояние между върховете.
  Да означим с r тежестта на това дърво, а с R - тежестта на оптималния маршрут от задачата за търговският пътник - TSP.
  (R е теглото на най-лекия затворен маршрут, минаващ точно по веднъж през всеки връх)

  Неравенството r < R е очевидно.

  Нека за изходният граф е изпълнено неравенството на триъгълника (т.е. преките пътища са по-къси от обиколните). Тогава:

  • в сила е неравенството R < 2r
  • минималното дърво може да се ползва за бързо построяване на приближено решение на TSP с тегло < 2r.

ИМЕ НА ЗАДАЧАТА: greedy

ВХОДЕН ФОРМАТ:

* Ред 1: Две цели числа, разделени с интервал: N и M
  N е броят на върховете в графа (N<=1000), 
  а M е броят на ребрата (M<=10000). 

* Редове от 2 до M+1: 
  Всеки ред съдържа 3 параметъра: I, J и L, които описват ребро. 
  I и J са върховете на реброто, L е теглото му.


ПРИМЕРЕН ВХОД (файл greedy.in):

6 10
2 5 3
4 6 2
1 6 1
4 5 2
6 3 2
1 2 5
1 3 4
2 4 4
3 2 1
6 2 1


ИЗХОДЕН ФОРМАТ:

* Редове от 1 до N-1: ребра на покриващото дърво
  Всеки ред съдържа по едно ребро от дървото, 
  като формата е същият както при входните данни.

ПРИМЕРЕН ИЗХОД:

1 2 5
1 3 4
2 4 4
2 5 3
4 6 2

• програма на Pascal
• примерни входни данни