Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 125
Текст из файла (страница 125)
главу 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 5 1 1 0 О 3~0 ~ 0: О, 4~0 ~ ! 0 31!О! -+ 2 1 -~4 5 'О~~1 2 ~ -~Д ~~~~ 5 ~ -1~3 33 + 4'агг'! 'Я:.: ——,,== ;,'==-.' '" . Д-~.~ Я-Я"' »(2Я Риа. 22.1. Два лрааатаалавиа ааорааатарввааасга 1рафа 3 4 4 6 !10 1 0 1 0 0,,' 2,'0 0 0 0 ! О' 3~0 О О О 4~0 ~ О 0 О О~ 5'о О 0 О~о 0 0 О 0 3 ~,-~ 4 б ~ -2О 5.Я б ! -' (6 ~"'3 —.1 43 о — -~2 ф О 42 — 5 (01 Рис. 22.2. Два представления ориентированного графа графов. Обычно более предпочтительно представление с помощью списков смежности, поскольку оно обеспечивает компактное представление разреженных (зрагае) графов, т.е. таких, для которых 1Е~ гораздо меньше 1У1~.
Большинство алгоритмов, представленных в данной книге, предполагают, что входной граф представлен именно в виде списка смежности. Представление при помощи матрицы смежности предпочтительнее в случае илотных (41епзе) графов, т.е. когда значение 1Е~ близко к 1Ц, или когда нам надо иметь возможность быстро определить, имеется ли ребро, соединяющие две данные вершины. Например, два алгоритма поиска кратчайшего пути для всех пар вершин, представленные в главе 25, используют представление графов именно в виде матриц смежности. Представление графа С = (К Е) в виде списка смяжкосвви (аб)асепсу-1151 гергеаеп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 предлагается вариант списков смежности, позволяющий ускорить поиск ребер). Представление графа С = (1Г, Е) с помощью матрицы смежности (ао1аселсу-ша1пх гергезепгабол) предполагает, что вершины перенумерованы в некотором порядке числами 1, 2,..., [У[.
В таком случае представление графа С с использованием матрицы смежности представляет собой матрицу А = (а; ) размером [Ц х Щ, такую что 1 если (1,1) б Е, а;1 —— 0 в противном случае. На рис. 22.1в и 22.2в показаны представления с использованием матрицы смежности неориентированного и ориентированного графов, показанных на рис. 22.1а и 22.2а соответственно. Матрица смежности графа требует объем памяти, равный 9 [Уз), независимо от количества ребер графа. Обратите внимание на симметричность матрицы смежности на рис. 22.1в относительно главной диагонали. Определим транспонированную (ггапзрозе) матрицу А = (аб) как матрицу А = (аЦ, у которой ат = а;. Поскольку граф неориентирован, (и, и) и (и, и) представляют одно и то же ребро, так что матрица смежности неориентированного графа совпадает с транспонированной матрицей смежности, т.е.
А = А~. В ряде приложений это свойство позволяет хранить только элементы матрицы, находящиеся на главной диагонали и выше нее, что позволяет почти в два раза сократить необходимое количество памяти. Часть Ч!. Алгоритмы для работы с графами 612 Так же, как и представление со списками смежности, представление с матрицами смежности можно использовать для взвешенных графов. Например, если С = (У,Е) — взвешенный граф с весовой функцией ю, то вес ю (и, и) ребра (и, и) е Е хранится в записи в строке и и столбце и матрицы смежности. Если ребро не существует, то в соответствующем элементе матрицы хранится значение н|г„хотя для многих приложений удобнее использовать некоторое значение, такое как О или оо. Хотя список смежности асимптотически, как минимум, столь же эффективен в плане требуемой памяти, как и матрица смежности, простота последней делает ее предпочтительной при работе с небольшими графами.
Кроме того, в случае невзвешенных графов для представления одного ребра достаточно одного бита, что позволяет существенно сэкономить необходимую для представления память. Упражнения 22.1-1. Имеется представление ориентированного графа с использованием списков смежности. Как долго будут вычисляться исходящие степени всех вершин графа? А входящие степени? 22.1-2. Имеется представление с использованием списков смежности полного бинарного дерева с 7 вершинами. Приведите его представление с использованием матрицы смежности (считаем, что вершины пронумерованы от 1 до 7, как в бинарной пирамиде).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
