Алгоритмы - построение и анализ (1021735), страница 123
Текст из файла (страница 123)
в) Докажите, что процедура 1.СА правильно выводит наименьших общих предков для каждой пары (и, и) Е Р. Глава 21. Структуры данных для непересекающихся множеств 605 г) Проанализируйте время работы процедуры ЬСА в предположении, что используется реализация непересекающихся множеств из раздела 21.3. Заключительные замечания Многие важные результаты о структурах данных для непересекающихся множеств в той или иной степени принадлежат Таржану (Таг1ап). В частности, именно им [290, 292) установлена точная верхняя граница с применением очень медленно растущей инверсии а (т, и) функции Аккермана (Аскеппапп).
(Функция Аь (т'), используемая в разделе 21.4, подобна функции Аккермана, а функция ст (и) — ее инверсии. Для всех мыслимых значений т и и как а (и), так и а (т, и) не превышают 4.) Верхняя граница О (т 1к' и) была доказана несколько ранее Хопкрофтом (Норсгой) и Ульманом ((Л1шап) (5, 155). Материал раздела 21.4 основан на более позднем анализе Таржана (294], который, в свою очередь, опирается на анализ Козена (Кохеп) [193].
Харфст (НагЫ) и Рейнгольд (КешяоЫ) [139] разработали версию доказательства полученных Таржаном оценок при помощи потенциалов. Таржан и ван Леувен (чап Ьееиттел) [295] рассмотрели разные варианты эвристики со сжатием пути, включая однопроходные варианты, которые эффективнее двухпроходных в силу меньшего постоянного множителя. Позже Харфст и Рейнгольд [! 39] показали, какие (небольшие) изменения следует внести в потенциальную функцию для адаптации их анализа сжатия пути к однопроходному варианту Таржана. Габон (баЬотт) и Таржан [103] показали, что в некоторых приложениях операции над непересекающимися множествами могут выполняться за время О (т).
Таржан [291] показал, что для операций над произвольными структурами данных для непересекающихся множеств, удовлетворяющими определенным техническим условиям, нижняя граница времени работы равна П (та (т, и)). Позже эта нижняя граница была обобщена Фредманом (Ргейпап) и Саксом (Бака) [97], которые показали, что в наихудшем случае эти операции требуют обращения к П (т а (т, и) ) словам памяти длиной !к и битов.
ЧАСТЬ У1 Алгоритмы для работы с графами Введение Графы представляют собой распространенные структуры в информатике, и алгоритмы для работы с графами очень важны. Имеются сотни интересных вычислительных задач, сформулированных с использованием графов. В этой части мы коснемся только некоторых наиболее важных из них. В главе 22 рассматриваются вопросы представления графов в компьютере и обсуждаются алгоритмы, основанные на обходе графа в ширину и в глубину. Приведены два применения обхода в глубину — топологическая сортировка ориентированного ациклического графа и разложение ориентированного графа на сильно связные компоненты.
В главе 23 описывается вычисление остовного дерева минимального веса. Такое дерево представляет собой набор ребер, связывающий все вершины графа с наименьшим возможным весом (каждое ребро обладает некоторым весом). Эта задача решается при помощи жадного алгоритма (см. главу 16).
В главах 24 и 25 рассматривается задача вычисления кратчайшего пути межау вершинами, когда каждому ребру присвоена некоторая длина или вес. Глава 24 посвящена вычислению кратчайшего пути из одной вершины во все остальные, а в главе 25 рассматривается поиск кратчайших путей для всех пар вершин. И наконец, в главе 26 рассматривается задача о максимальном потоке материала в сети (ориентированном графе) с определенным источником вещества, стоком и пропускной способностью каждого ребра. К этой общей задаче сводятся многие другие, так что хороший алгоритм ее решения может использоваться во многих приложениях.
При описании времени работы алгоритма над данным графом С = (К Е) мы обычно определяем размер входного графа в терминах количества его вершин [1:[ и количества ребер [Е[ графа, т.е. размер входных данных описывается двумя, а не одним параметром. Для удобства и краткости в асимптотических обозначениях (таких, как О и 9-обозначения), и только в них, символ У будет означать [1'[, а символ Š— [Е[, т.е. когда мы будем говорить "время работы алгоритма равно О (Ъ'Е)", то это означает "время работы алгоритма равно О ([Ъ'[ [Е[)". Такое соглашение позволяет сделать формулы для времени работы более удобочитаемыми без риска неоднозначности.
Еще одно соглашение принято для псевдокода. Мы обозначаем множество вершин графа С как 1~ [С), а множество ребер — как Е [С1, т.е. в псевдокоде множества вершин и ребер рассматриваются как атрибуты графа. ГЛАВА 22 Элементарные алгоритмы для работы с графами В этой главе рассматриваются методы представления графов, а также обход графа. Под обходом графа понимается систематическое перемещение по ребрам графа, при котором посещаются все его вершины.
Алгоритм обхода графа может многое сказать о его структуре, поэтому многие другие алгоритмы начинают свою работу с получения информации о струкгуре путем обхода графа. Многие алгоритмы для работы с графами организованы как простое усовершенствование базовых алгоритмов обхода графа. В разделе 22.1 рассматриваются два наиболее распространенных способа представления графов — списки смежных вершин и матрица смежности. В разделе 22.2 представлен простой алгоритм обхода графа, который называется поиском в ширину, и соответствующее этому алгоритму дерево. В разделе 22.3 представлен алгоритм поиска в глубину и доказываются некоторые свойства этого вида обхода графа.
В разделе 22.4 вы познакомитесь с первым реальным применением поиска в глубину — топологической сортировкой ориентированного ациклического графа. Еще одно применение поиска в глубину — поиск сильно связных компонентов графа — приводится в разделе 22.5. 22.1 Представление графов Имеется два стандартных способа представления графа С = (К, Е): как набора списков смежных вершин или как матрицы смежности. Оба способа представления применимы как для ориентированных, так и для неориентированных Часть Ч1. Алгоритмы для работы с графами 610 2 3 4 3 1 1 0 О 3~0 ~ 0: О, 4~0 ~ ! 0 31!О! Риа.
22.1. Два лрааатаалавиа ааорааатарввааасга 1рафа 3 4 б 6 !10 1 0 1 0 0,,' 2,'0 0 0 0 ! О' 3~0 О О О 4~0 ~ О 0 О О~ 3'о О 0 0 О 0 2; -4 4; ~/"~ 3 ~ — ~ ~ б ( -оа4, О.Я Рис. 22.2. Два представления ориентированного графа графов. Обычно более предпочтительно представление с помощью списков смежности, поскольку оно обеспечивает компактное представление разреженных (зрагае) графов, т.е.
таких, для которых 1Е~ гораздо меньше 1У1~. Большинство алгоритмов, представленных в данной книге, предполагают, что входной граф представлен именно в виде списка смежности. Представление при помощи матрицы смежности предпочтительнее в случае илотных (41епзе) графов, т.е. когда значение 1Е~ близко к 1Ц, или когда нам надо иметь возможность быстро определить, имеется ли ребро, соединяющие две данные вершины. Например, два алгоритма поиска кратчайшего пути для всех пар вершин, представленные в главе 25, используют представление графов именно в виде матриц смежности. Представление графа С = (К Е) в виде списка смяжкосвви (аб)асепсу-11М гергеаеп1абоп) использует массив А46 из Щ списков, по одному для каждой вершины из У. Для каждой вершины и Е 7" список А46 1и) содержит все вершины е, такие что (34,42) Е Е, т.е.
Аа(3 134) состоит из всех вершин, смежных с и в графе С (список может содержать и не сами вершины, а указатели на них). Вершины в каждом списке обычно хранятся в произвольном порядке. На рис. 22.1б показано такое представление графа, изображенного на рис.
22.1а (на рис. 22.10 представлена его матрица смежности). Аналогично, на рис. 22.2б и рис. 22.20 показаны список и матрица смежности ориентированного графа, изображенного на рис. 22.2а. Глава 22. Элементарные алгоритмы для работы с графами 611 Если С вЂ” ориентированный граф, то сумма длин всех списков смежности равна [Е], поскольку ребру (и,и) однозначно соответствует элемент о в списке Аф [и]. Если С вЂ” неориентированный граф, то сумма длин всех списков смежности равна 2 [Е[, поскольку ребро (и, и), будучи неориентированным, появляется в списке Аф [и] как и, и в списке Аф [и] — как и. Как для ориентированных, так и для неориентированных графов представление в виде списков требует объем памяти, равный 9 (У + Е).
Списки смежности легко адаптируются для представления взвешенных графов (~не1йлгес$ агарь), т.е. графов, с каждым ребром которых связан определенный вес (юе(ййг)„обычно определяемый весовой функцией (юе1я1п Гипсбоп) ш: Е -+ К. Например, пусть С = (1г, Е) — взвешенный граф с весовой функцией и. Вес и (и, и) ребра (и, и) е Е просто хранится вместе с вершиной и в списке смежности и. Представление с помощью списков смежности достаточно гибко в том смысле, что легко адаптируется для поддержки многих других вариантов графов.
Потенциальный недостаток представления при помощи списков смежности заключается в том, что при этом нет более быстрого способа определить, имеется ли данное ребро (и, и) в графе, чем поиск и в списке А4 [и]. Этот недостаток можно устранить ценой использования асимптотически большего количества памяти и представления графа с помощью матрицы смежности (в упражнении 22.1-8 предлагается вариант списков смежности, позволяющий ускорить поиск ребер).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
