Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 137
Текст из файла (страница 137)
В задаче автономного поиска нанменынего общего предка (о1Т-11пе 1еаз1-сопнпоп-апсезгог ргоЫеш) даны юрневое дерево Т и произвольное множество Р = ((и,и)) неупорядоченных пар узлов в Т. Для каждой пары узлов из Р требуется найти их наименьший общий предок. Для решения задачи автономного поиска наименьшего общего предка осуществляется обход дерева Т с помощью приведенной ниже процедуры с начальным вызовом 1.СА(Т.
тоо1). Предполагается, что перед вызовом процедуры все узлы помечены как ШН1ТЕ (белые). 1.СА(и) 1 МАКЕ-БЕТ(и) 2 р11йзз-Бет(и). аисев1от = и 3 Гог каждого узла и, дочернего по отношению к и в Т 4 1.СА(и) 5 П1Ч1О1Ч(и, и) 6 т11нВ-БЕТ(и).апссвгот = и 7 и.со1от = ВЕАСК 8 Гог каждого узла и, такого, что (и, и) е Р 9 1Т и. со1от == ВЕАСК 10 рпп1 "Наименьшим общим предком" и и и является' Р1хп-Бет(и). апссв1от а.
Докажите, что строка 1О выполняется только один раз для каждой пары (и,и) Е Р. Глава Л. Структуры данные для ненересекающичся мнозсеств б21 6. Докажите, что в момент вызова ЬСА(и) количество множеств в структуре данных для непересекающихся множеств равно глубине и в Т. в. Докажите, что процедура 1.СА правильно выводит наименьшие общие предки и и о для каждой пары (и, о] Е Р.
л Проанализируйте время работы процедуры 1.СА в предположении, что используется реализация структуры непересекающихся множеств из раздела 21.3. Заключительньзе замечания Многие важные научные результаты о структурах данных для непересекающихся множеств в той нли иной степени принадлежат Р.Э. Таржану (В.Е. Таг]ап). В частности, именно им [326,328] дана первая точная верхняя граница с применением очень медленно растущей инверсии а(т,и) функции Аккермана (Аскеппапп).
(Функция Ан(~), используемая в разделе 21.4, подобна функции Аккермана, а функция «к(и) — обратной ей. Для всех мыслимых значений т и и как гк(и), так и а(т, и) не превышают 4.) Верхняя граница 0(т 18' и) была доказана несколько ранее Хопкрофтом (Норсгой) и Ульманом (ЫПшап) [5,! 78]. Материал раздела 21.4 основан на более позднем анализе Таржана [330], который, в свою очередь, опирается на анализ Козена (Котел) [219]. Харфст (Нагй1) и Рейнгольд (Кешйо!б) [160] разработали версию доказательства полученных Таржаном оценок с помощью потенциалов. Таржан и ван Леувен (чаи 1.еешнеп) [331] рассмотрели разные варианты эвристики со сжатием пути, включая однопроходные варианты, которые зффекгивнее двухпроходных в силу меньшего постоянного множителя.
Позже Харфст и Рейнгольд [160] показали, какие небольшие изменения следует внести в потенциальную функцию для адаптации их анализа сжатия пути к однопроходному варианту Таржана. Габон (баЬотв) и Таржан [120] показали, что в некоторых приложениях операции над непересекающимися множествами могут выполняться за время 0(т). Таржан [327] показал, что для операций над произвольными структурами данных для непересеканлцихся множеств, удовлетворяющими определенным техническим условиям, нижняя граница времени работы равна й(т а(т, и)). Позже зта нижняя граница была обобщена Фредманом (Ргебшап) и Саксом (Бака) [112], которые показали, что в наихудшем случае эти операции требуют обращения к й(т гк(т, и)) (18 и)-битовым словам памяти.
И Алгоритмы для работы с графами Введение Графы представляют собой распространенные структуры в информатике, и алгоритмы для работы с графами очень важны. Имеются сотни интересных вычислительных задач, сформулированных с использованием графов. В этой части мы коснемся только некоторых наиболее важных из них. В главе 22 рассматриваются вопросы представления графов в компьютере и обсуждаются алгоритмы, основанные на обходе ~рафа в ширину и в глубину. Здесь приведены два применения обхода в глубину — топологическая сортировка ориентированного ацикпического графа и разложение ориентированного графа на сильно связные компоненты.
В главе 23 описывается вычисление остовного дерева минимального веса. Такое дерево представляет собой набор ребер, связывающий все вершины графа с наименьшим возможным весом (каждое ребро обладает некоторым весом). Эта задача служит хорошим примером применения жадных алгоритмов (см. главу 16). В главах 24 и 25 рассматривается задача вычисления кратчайшего пути между вершинами, когда каждому ребру присвоена некоторая длина или вес. Глава 24 посвящена вычислению кратчайшего пути из одной вершины во все остальные, а в главе 25 рассматривается поиск кратчайших путей для всех пар вершин.
И наконец в главе 26 рассматривается задача о вычислении максимального потока материала в сети (ориентированном графе) с определенным источником вещества, стоком и пропускной способностью каждого ребра. К этой общей задаче сводятся многие другие, так что хороший алгоритм ее решения может использоваться во многих приложениях. При описании времени работы алгоритма над заданным графом С = ($~, Е) мы обычно определяем размер входного графа в терминах количества его вершин Щ и ребер (Е), т.е, размер входных данных описывается двумя, а не одним параметром. Для удобства и краткости в асимптотических обозначениях (таких, как 0 и О-обозначения), и только в них, символ И будет означать ~Ц, а символ Š— ~Е~, те.
когда мы будем говорить "время работы алгоритма равно 0(Ъ'Е)", то Часть ГТ аггоритмы дла работы с графами б?5 это означает "время работы алгоритма равно О(Щ )ЕО". Такое соглашение позволяет сделать формулы для времени работы более удобочитаемыми без риска неоднозначного толкования. Бще одно соглашение принято для псевдокода. Мы обозначаем множество вершин графа С как С. й, а множество ребер — как С. Е, т.е. в псевдокоде множества вершин и ребер рассматриваются как атрибуты графа. Глава 22. Элементарные алгоритмы для работы с графами В этой главе рассматриваются методы представления графов, а также их обхода.
Под обходом графа понимается систематическое перемещение по ребрам графа, при котором посещаются все его вершины. Алгоритм обхода графа может многое сказать о его структуре, поэтому многие алгоритмы начинают свою работу с получения информации о структуре путем обхода графа. Некоторые другие алгоритмы для работы с графами организованы как простое усовершенствование базовых алгоритмов обхода графа. В разделе 22.1 рассматриваются два наиболее распространенных способа представления графов — списки смежных вершин и матрица смежности. В разделе 22.2 представлены простой алгоритм обхода графа, который называется поиском в ширину, и соотвегствуюшее этому алгоритму дерево.
В разделе 22.3 представлен алгоритм поиска в глубину и доказываются некоторые свойства этого вида обхода графа. В разделе 22.4 вы познакомитесь с первым реальным применением поиска в глубину — топологической сортировкой ориентированного ациклического графа. Еще одно применение поиска в глубину — поиск сильно связных компонентов графа — приводится в разделе 22.5.
22.1. Представление графов Имеется два стандартных способа представления графа С = (Ъ; Е): как набора списков смежных вершин и как матрицы смежности. Оба способа представления применимы как для ориентированных, так и для неориентированных графов. Обычно более предпочтительным является представление с помощью списков смежности, поскольку оно обеспечивает компактное представление раз~тежеииых (зрагае) графов, т.е. таких, для которых ~Е( гораздо меньше, чем )Ц .
Большинство алгоритмов, представленных в данной книге, предполагают, что входной граф представлен именно в виде списка смежности. Представление с помошью матрицы смежности предпочтительнее в случае плотных (пензе) графов (т.е. когда значение (Е! близко к (Ц~) или когда необходимо иметь возможность быстро определить, существует ли ребро„соединяющие две данные вершины. Например, в главе 25 два алгоритма поиска кратчайшего пути для всех пар вершин используют представление графов именно в виде матриц смежности. Глава 22.
Элеыетяарлые овгоритмы блл рабаты с грагргьии б27 1 2 3 4 5 (б) (а) (в) Рис 22.1. Два представления неориентированного графа. (а) Неориентированный граф С с пятью вершинами и семью ребрами. (6) Представление С с помощью списяов смюености. (в) Представление С с помощью матрицы смежности. ! 2 3 4 5 6 2:г .~~+я':, 3 ':ас! (бг":-7.;;"б(:~:~ 4 ].+ ('й:~~;~ 5 (':-.,"],"4;(ГЯ б (,','( (б'~~~~~ 1 2 3 4 5 б (а) (6) (в) Рис. 22.2. Два представления ориентированного графа. (а) Ориентированный граф С с шестью вершинами и восемью ребрами. (б) Представление С с помощью сплавов сменности.
(в) Представление С с помощью матрицы сменности. Представление графа С = (КЕ) в виде списка смежности (а(1)асепсу-1(з1 гергевеп(абоп) использует массив А4 из ]17] списков, по одному для каждой вершины из 17. для каждой вершины и б $' список смежности А((7']и] содержит все вершины п, такие, что (и, и) е Е, т.е. А(() ]и] состоит из всех вершин, смежных с и в графе С (список может содержать и не сами вершины, а указатели на них). Поскольку списки смежности представляют ребра графа, в псевдокоде массив А(() рассматривается как атрибут графа, так же, как мы рассматриваем множество ребер Е. Таким образом, в псевдокоде вы встретитесь с обозначениями наподобие С. А((7'[и].
На рис. 22.1, (б) показано представление неориентированного графа на рис. 22.1,(а) с помощью списков смежности. Аналогично на рис. 22.2,(б) показано представление с помощью списков смежности ориентированного графа на рис. 22.2, (а). Если С является ориентированным графом, то сумма длин всех списков смежности равна ]Е], поскольку ребру (и,о) однозначно соответствует элемент е в списке А(()]и]. Если же С представляет собой неориентированный граф, то сумма длин всех списков смежности равна 2]Е], поскольку ребро (и, о), будучи иеориеитированиым, появляется как в списке смежности и, так и в списке е.
Как для ориентированных, так и для неориентированных графов представление в виде списков требует обьема памяти, равного 9((7 + Е). Списки смежности легко адаптируются для представления езаенгениых графов (ше(я))1е(1 (рнрп), т.е. графов, с каждым ребром которых связан определенный иес Часть ~7. Алгоритмы оаа раооты с графами (аге18пг), обычно определяемый весовой функцией (пе18пг йшсйоп) и; Š— + И.
Например, пусть С = ((г, Е) — взвешенный граф с весовой функцией ш. Вес га(п, и) ребра (и, с) Е Е просто хранится вместе с вершиной с в списке смежности и. Представление с помощью списков смежности достаточно гибко в том смысле, что легко адаптируется для поддержки многих других вариантов графов. Потенциальный недостаток представления с помощью списков смежности заключается в том, что при этом нет более быстрого способа определить, имеется ли данное ребро (и, с) в графе, чем поиск с в списке Аь(г 1и].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
