Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. > 20.61.Покажите в стиле рис
|
|
> 20.61. Покажите в стиле рис. 20.14 результат вычисления дерева MTS сети, определение которой дано в упражнении 20.26, с помощью алгоритма Борувки.
о 20.62. Почему программа 20.9 выполняет проверку find перед тем, как выполнять операцию union? Указание. Рассмотрите ребра одинаковой длины.
о 20.63. Объясните, почему значение b(h) может быть равным нулю (программа 20.9) в проверке, которая защищает операцию union.
• 20.64. Дайте описание семейства графов с V вершинами Е ребрами, для которых число ребер, не отвергнутых в процессе выполнения всех этапов алгоритма Борувки, настолько велико, что возникают условия, характерные для худшего случая.
20.65. Разработайте реализацию алгоритма Борувки, основанную на предварительной сортировке ребер.
о 20.66. Разработайте реализацию алгоритма Борувки, который использует для представления поддеревьев MST двухсвязные кольцевые списки, благодаря чему можно выполнять слияние и переименование поддеревьев за время, пропорциональное Е, на каждом этапе (благодаря чему отношения эквивалентности в АТД не нужны).
РИСУНОК 20.16. АЛГОРИТМ БОРУВКИ ПОСТРОЕНИЯ ДЕРЕВА MST
Для построения дерева MST в данном примере достаточно всего лишь четырех этапов (снизу вверх).
Часть 5. Алгоритмы на графах
о 20.67. Проведите эмпирические исследования для сравнения реализации алгоритма Борувки из упражнения 20.66 с реализацией, приведенной в тексте (программа 20.9), на различных типах взвешенных графов (см. упражнения 20.9-20.14).
• 20.68. Проведите эмпирические исследования для составления таблицы количества эта
пов и числа ребер, обрабатываемых на каждом этапе в алгоритме Борувки для различ
ных типов взвешенных графов (см. упражнения 20.9—20.14).
20.69. Разработайте реализацию алгоритма Борувки, обеспечивающую построение нового графа (образующую лес, в котором каждая вершина представляет одно дерево) на каждом этапе.
• 20.70. Напишите клиентскую программу, которая выполняет графическую анимацию
динамики алгоритма Борувки (см. упражнения 20.52 и 20.60). Проверьте полученную
программу на случайных эвклидовых графах с близкими связями и на сетчатых гра
фах (см. упражнения 20.17 и 20.19), используя при этом столько точек, сколько мож
но обработать за приемлемый промежуток времени.