Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Часть 5. Алгоритмы на графах. Свойство 21.4. Для всех сетей и всех приоритетных функций мы можем вычислить остовное дерево с помощью PFS за время
|
|
Свойство 21.4. Для всех сетей и всех приоритетных функций мы можем вычислить остовное дерево с помощью PFS за время, пропорциональное времени, необходимому для V вставок (insert), V удалений минимума (delete the minimum) и применения Е операций уменьшения ключа (decrease key) в очереди с приоритетами размера не более V.
Доказательство: Этот факт следует непосредственно из реализаций программ 20.7 и 21.1, основанных на очереди с приоритетами. Он дает завышенную верхнюю границу, поскольку размер очереди с приоритетами часто намного меньше V, особенно в программе 20.7. ■
Свойство 21.5. При реализации алгоритма Дейкстры с PFS, использующего полное бинарное дерево для представления очереди с приоритетами, мы можем вычислить любое SPT за время, пропорциональное Е lg V.
Доказательство: Этот результат является прямым следствием свойства 21.4. ■
Свойство 21.6. Для заданного графа с V вершинами и Е ребрами обозначим через d плотность E/V. Если d < 2, то время выполнения алгоритма Дейкстры пропорционально V lgV. В противном случае мы можем улучшить время выполнения не менее чем на коэффициент lg(E/V), т.е. О(Е lgd V) (которое линейно, если Е составляет, по крайней мере, Vl*e), при использовании для очереди с приоритетами полного [Е/ V]-арного дерева.
Доказательство: Этот результат непосредственно отражает свойство 20.12 и реализацию очереди с приоритетами при помощи нескольких полных бинарных деревьев, которая будет обсуждаться несколько ниже. ■
Таблица 211 Алгоритмы поиска по приоритету__________________________________
Все эти четыре классических алгоритма обработки графов могут быть реализованы при помощи PFS, т.е. обобщенного, основанного на очередях с приоритетами поиска на графе, который строит остовные деревья, перемещая в дерево одно ребро за один шаг. Детали динамики поиска зависят от представления графа, реализации очереди с приоритетами, а также реализации PFS, однако деревья поиска в общем характеризуют различные алгоритмы, как показано на рисунках, на которые приводятся ссылки в четвертом столбце.
Алгоритм Приоритет Результат Рисунок
Таблица 21.1 подводит итог известных сведений о четырех основных рассмотренных нами алгоритмах PFS. Они отличаются только используемой функцией вычисления приоритета, и эта разница приводит к остовным деревьям, которые полностью отличаются одно от другого по внешнему виду (как и должно быть). Например, на рисунках, к которым отсылает нас таблица (и для многих других графов), дерево DFS является высоким и тонким, дерево BFS - коротким и толстым; SPT похоже на дерево BFS, но не такое