Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Нахождение на графе минимального остовного дерева

Поиск:
Примем без доказательства следующее свойство MST ( minimal spanning tree - минимальное остовное дерево на англ.).

В графе G=(V, E) рассмотрим U - некоторое подмножество V, такое что U и V-U не пусты. Пусть (u, v) - ребро наименьшей стоимости, одна вершина которого - u принадлежит U, а другая - v принадлежит V-U. Тогда существует некоторое MST, содержащее ребро (u, v).

Пусть в примере ниже U = B, C. Тогда существует MST, содержащее ребро (C, E).
user posted image


На этом свойстве основаны два известных алгоритма.

Алгоритм Прима.


    

Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U.

Код

Положить в U любую вершину;   // изначально U - пусто.
while ( V-U не пусто )
{
   Выбрать ребро (u, v) наименьшей стоимости,
    u из U, v из V-U;
   Добавить v к U (и убрать из V-U); 
}


Очевидно, данный алгоритм имеет сложность O(V2)

Алгоритм Краскала.


    

В отличие от алгоритма Прима, этот алгоритм не требует прохода по всем вершинам для нахождения ребра с минимальным весом. Вместо этого он использует 'жадный' подход.

Работаем с вершинами, а не с ребрами G. Это дает нам V связных компонент. Будем увеличивать их размер по ребру за раз. Число ребер, необходимое для остовного дерева: V-1. Граф связен, а значит E содержит как минимум такое их количество.

Код

Создаем список вершин L, в неубывающем по весу порядке
while ( число отмеченных вершин < V-1 )
{
  w = L.Remove();  // удалить из головы списка
  if ( w соединяет две несвязных компоненты )
        отметить w и добавить к MST
   else  // w - внутри компоненты
     не отмечать w  // это приведет к циклу в MST
  }  


Сложность алгоритма составляет O(E*lg E).
Сайт: algolist.da.ru





Файлы:
rtree2.gif

Просмотров: 3581

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную