Алгоритмы - построение и анализ (1021735), страница 131
Текст из файла (страница 131)
Поиск в глубину широю используется с конца 1950-х годов, в особенности в программах искусственного интеллекта. Таржан [289] разработал алгоритм поиска сильно связных компонентов за линейное время. Алгоритм из раздела 22.5 взят у Ахо (АЬо), Хопкрофта и Ульмана (Ы1!шап) [6], которые ссылаются на неопубликованную работу Косараю (В.К. Козага]и) и работу Шарира (8Ьапг) [276]. Габов (ОаЬотч) [101] разработал алгоритм для поиска сильно связных компонентов, который основан на сжатых циклах и использует два стека для обеспечения линейного времени работы.
Кнут (КпиГЬ) [182] первым разработал алгоритм топологической сортировки за линейное время. ГЛАВА 23 Минимальные остовные деревья При разработке электронных схем зачастую необходимо электрически соединить контакты нескольких компонентов. Для соединения множества из и контактов мы можем использовать некоторую компоновку из п — 1 проводов, каждый из которых соединяет два контакта. Обычно желательно получить компоновку, которая использует минимальное количество провода. Мы можем смоделировать эту задачу при помощи связного неориентированного графа С = (Ъ; Е), где $' — множество контактов, Š— множество возможных соединений между парами контактов, и для каждого ребра (и, и) й Е задан вес зл (и, и), определяющий стоимость (количество необходимого провода) соединения и и и. Мы хотим найти ациклическое подмножество Т С Е, которое соединяет все вершины и чей общий вес ш(Т) = ~.
'ш(и,и) (н,е)еТ минимален. Поскольку множество Т ациклическое и связывает все вершины, оно должно образовывать дерево, которое мы назовем остовным деревом (зрапп)пд псе) графа С (иногда используется термин "покрывающее дерево"). Задачу поиска дерева Т мы назовем задачей лоиска минимального остовного дерева (пппппшпзрапп1пя-нее ргоЫеш)'. На рис. 23.1 показан пример связного графа и его минимального остовного дерева. На ребрах указан их вес, а ребра минимального остов- ного дерева отдельно выделены цветом. Общий вес показанного дерева равен 37. 'По сути, термин "минимальное остовное дерево" означает "остовное дерево с минимальным весом". Мы не минимизируем, например, количество ребер в Т, поскольку все остовные деревья имеют ровно ٠— 1 ребер согласно теореме Б.2.
Глава 23. Минимальные остовные деревья 'ь), Рис. 23.1. Минимальное остовное дерево связного графа Приведенное дерево не единственное: удалив ребро (Ь, с) и заменив его ребром (а, Ь), мы получим другое остовное дерево с тем же весом 37. В этой главе мы рассмотрим два алгоритма решения задачи поиска минимального остовного дерева — алгоритм Крускала (КпЫса1) и Прима (Рптп). Каждый из них легко реализовать с помощью обычных бинарных пирамид, получив время работы О (Е 1к Ъ').
При использовании фибоначчиевых пирамид алгоритм Прима можно ускорить до О (Е + Ъ' 1к Ъ'), что является весьма существенным ускорением при ~Ц << )Е!. Оба эти алгоритма — жадные (см. главу 16). На каждом шаге алгоритма мы выбираем один из возможных вариантов. Жадная стратегия предполагает выбор варианта, наилучшего в данный момент. В общем случае такая стратегия не гарантирует глобально оптимального решения задачи, однако для задачи поиска минимального остовного дерева можно доказать, что определенные жадные стратегии дают нам остовное дерево минимального веса.
Хотя настоящую главу можно читать независимо от главы 1б, жадные алгоритмы, представленные здесь, наглядно демонстрируют классическое применение изложенных в этой главе теоретических основ. В разделе 23.1 описана общая схема построения минимального остовного дерева, которая наращивает остовное дерево по одному ребру. В разделе 23.2 приведены два пути реализации обобщенного алгоритма. Первый алгоритм (Крускала) похож на алгоритм поиска связных компонентов из раздела 21.1.
Второй алгоритм (Прима) подобен алгоритму поиска кратчайшего пути Дейкстры (131)касса) из раздела 24.3. 23.1 Построение минимального остовного дерева Предположим, что у нас есть связный неориентированный граф С = (г', Е) с весовой функцией ю: Š— ~ К, и мы хотим найти минимальное остовное дерево Часть Ч1.
Алгоритмы для работы с графами для С. В этой главе мы рассмотрим два жадных алгоритма решения поставленной задачи. Оба рассматриваемых алгоритма имеют общую схему, согласно которой минимальное остовное дерево растет путем добавления к нему ребер по одному. Алгоритм работает с множеством ребер А, и инвариант цикла алгоритма выглядит следующим образом: Перед каждой очередной итерацией А представляет собой подмноже- ство некоторого минимального остовного дерева.
На каждом шаге алгоритма мы определяем ребро (и, о), юторое можно добавить к А без нарушения этого инварианта, в том смысле, что А 0 Г(и, о)) также является подмножеством минимального остовного дерева. Мы назовем такое ребро безопасным (за1е ебйе) для А, поскольку его можно добавить к А, не опасаясь нарушить инвариант. Оегчеис МБТ(С, и) А И 2 ттЫ1е А не является минимальным остовным деревом 3 до Найти безопасное для А ребро (и, с) 4 А — АО~(и,с)) 5 гетиги А Мы используем инвариант цикла следующим образом.
Инициализация. После выполнения строки 1 множество А тривиально удовлетворяет инварианту цикла. Сохранение. Цикл в строках 2-4 сохраняет инвариант путем добавления только безопасных ребер. Завершение. Все ребра, добавленные в А, находятся в минимальном остовном дереве, так что множество А, возвращаемое в строке 5, должно быть минимальным остовным деревом. Самое важное, само собой разумеется, заключается в том, как именно найти безопасное ребро в строке 3.
Оно должно существовать, посюльку когда выполняется строка 3, инвариант требует, чтобы существовало такое остовное дерево Т, что А С Т. Внутри тела цикла ттЫ1е А должно быть истинным подмножеством Т, поэтому должно существовать ребро (и, с) Е Т, такое что (и, с) ф А и (и, о)— безопасное для А ребро. В оставшейся части этого раздела мы приведем правило (теорема 23.1) для распознавания безопасных ребер. В следующем разделе описаны два алгоритма, которые используют это правило для эффективного поиска безопасных ребер. Глава 23.
Минимальные остовные деревья 647 15 „'г-5 а) Рис. 23.2. Два варианта представления разреза (5, У вЂ” Я) графа, приведенного на рис. 23.1 Начнем с определений. Разрпом (сит) (Я, Ъ' — Я) неориентированного графа С = (К Е) называется разбиение У, что проиллюстрировано на рис. 23.2 (вершины в множестве Я окрашены в черный цвет, а в множестве Ъ' — Я вЂ” в белый). Мы говорим, что ребро (та, о) Е Е пересекаева (сгоззез) разрез (5, У вЂ” Я), если один из его концов оказывается в множестве Я, а второй — в У вЂ” Я. Разрез согласован (гезрест) с множеством А по ребрам, если ни одно ребро из А не пересекает разрез. Ребро, пересекающее разрез, является легким (йй(тт), если оно имеет минимальный вес среди всех ребер, пересекающих разрез.
Заметим, что может быть несколько легких ребер одновременно. В общем случае мы говорим, что ребро является легким ребром, удовлетворяющим некоторому свойству, если оно имеет минимальный вес среди всех ребер, удовлетворяющих данному свойству. Наше правило для распознавания безопасных ребер дает следующая теорема. Теорема 23.1. Пусть 0 = (К Е) — связный неориентированный граф с действительной весовой функцией и, определенной на Е. Пусть А — подмножество Е, которое входит в некоторое минимальное остовное дерево С, (Я, У вЂ” Я) — разрез С, согласованный с А по ребрам, а (и, о) — легкое ребро, пересекающее разрез (Я, У вЂ” Я).
Тогда ребро (та, о) является безопасным для А. Доказалаельстао. Пусть Т вЂ” минимальное остовное дерево, которое включает А, и предположим, что Т не содержит ребро (та, и), поскольку в противном случае теорема доказана. Мы построим другое минимальное остовное дерево Т', Часть Ч1. Алгоритмы для работы с графами 648 Рис. 23.3.
Иллюстрация к доказатель- ству теоремы 23.1 которое включает А О ((и, и)), путем использования метода вырезания и вставки, показывая таким образом, что ребро (и, и) являе~ся безопасным для А. Ребро (и, и) образует цикл с ребрами на пути р от и к и в Т, как показано на рис. 23.3.
Поскольку и и и находятся на разных сторонах разреза (Я, У вЂ” Я), на пути р имеется как минимум одно ребро из Т, которое пересекает разрез. Пусть таким ребром является ребро (х, у). Ребро (х, у) не входит в А, поскольку разрез согласован с А по ребрам. Так как (х, у) является единственным путем от и к и в Т, его удаление разбивает Т на два компонента. Добавление (и, и) восстанавливает разбиение, образуя новое остовное дерево Т' = Т вЂ” ((х, у)) 0 ((и, и)).
Теперь мы покажем, что Т' — минимальное остовное дерево. Поскольку (и, и) — легкое ребро, пересекающее разбиение (Я, У вЂ” Я), и (х, у) также пересекает это разбиение, ю (и, и) < ю (х, у). Следовательно, ю (Т') = ю(Т) — ю(х,у) + ю(и,и) < ю(Т). Однако Т вЂ” минимальное остовное дерево, так что ю (Т) < ю (Т'). Следовательно, Т' также должно быть минимальным остовным деревом. Остается показать, что (и, и) действительно безопасное ребро для А. Мы имеем А С Т', поскольку А С Т и (х, у) ф А. Таким образом„А 0 ((и, и)) С Т' и, поскольку Т' — минимальное остовное дерево, ребро (и, и) безопасно для А.д Теорема 23.1 помогает нам лучше понять„как работает процедура Оечнк)с МБТ.
В процессе работы алгоритма множество А всегда ацикпическое; в противном случае минимальное остовное дерево, включающее А, содержало бы цикл, что приводит к противоречию. В любой момент выполнения алгоритма граф Сл = = (Ъ; Е) представляет собой лес и каждый из связных компонентов С,~ является Глава 23. Минимальные остовные деревья 649 деревом. (Некоторые из деревьев могут содержать всего одну вершину, например, в случае, когда алгоритм начинает работу: множество А в этот момент пустое, а лес содержит Щ деревьев, по одному для каждой вершины.) Кроме того, любое безопасное для А ребро (и, и) соединяет различные компоненты СА, поскольку множество А О ((и, и) ) должно быть ациклическим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
