Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. > 20.53.Покажите в стиле рис
|
|
> 20.53. Покажите в стиле рис. 20.12 результат вычисления дерева MST по алгоритму Крускала для сети, определение которой дано в упражнении 20.26.
о 20.54. Проведите эмпирические исследования на различных видах взвешенных графов с целью определения длины самого длинного ребра дерева MST и числа ребер графа, длина которых не превосходит длины этого ребра (см. упражнения 20.9-20. 14).
• 20.55. Разработайте реализацию АТД поиска-объединения, которое выполняет операцию find за постоянное время и операцию union за время, пропорциональное lg V
20.56. Проведите эмпирическое тестирование на различных видах взвешенных графов с целью сравнить полученную вами при решении упражнения 20.55 реализацию АТД с взвешенной операцией поиска-объединения с делением пополам (программа 1.4), когда алгоритм Крускала представляет собой клиентскую программу (см. упражнения 20.9—20.14). Выведите затраты на сортировку ребер отдельно с таким расчетом, чтобы можно было изучать их влияние на общие затраты и на часть расходов, связанных с АТД поиска-объединения.
Часть 5. Алгоритмы на графах
20.57. Разработайте реализацию на основе идеи, описанной в тексте, в рамках которой мы интегрируем алгоритм Крускала с быстрой сортировкой с тем, чтобы проверить каждое ребро на принадлежность дереву MST, если нам известно, что все ребра с малым весом подверглись проверке.
о 20.58. Внесите в алгоритм Крускала такие изменения, чтобы сделать возможной реализацию двух функции АТД, которые заполняют вектор, индексированный именами вершин, поставляемый клиентской программой. Этот вектор осуществляет разбиение вершин на к кластеров, обладающих тем свойством, что ни одно ребро с длиной, большей d, не соединяет две вершины из различных кластеров. Первая функция принимает к в качестве аргумента и возвращает d; вторая функция принимает d как аргумент и возвращает к. Проверьте свою программу на случайных эвклидовых графах с близкими связями и на сетчатых графах (см. упражнения 20.17 и 20.19) различных размеров, варьируя значения к и d.
20.59. Разработайте реализацию алгоритма Прима, в основу которой положена предварительная сортировка ребер.
• 20.60. Напишите клиентскую программу, которая выполняет графическую анимацию динамики алгоритма Крускала (см. упражнение 20.52). Проверьте полученную программу на случайных эвклидовых графах с близкими связями и на сетчатых графах (см. упражнения 20.17 и 20.19), используя при этом столько точек, сколько можно обработать за приемлемый промежуток времени.