Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 138
Текст из файла (страница 138)
Этот недостаток можно устранить ценой использования асимптотически большего количества памяти в представлении графа с помощью матрицы смежности. (В упр. 22.1.8 предлагается вариант списков смежности, позволяющий ускорить поиск ребер.) Представление графа С = ($; Е) с помощью матрицы смежности (аб)асепсу-шаП1х гергезеп1айоп) предполагает, что вершины графа перенумерованы в некотором произвольном порядке числами 1,2,..., Щ. В таком случае представление графа С с использованием матрицы смежности представляет собой матрицу А = (аб) размером Щ х )Ц, такую, что ~' 1, если (1, з) е Е, ап —— ( О в противном случае .
На рис. 22.1, (в) и 22.2, (в) показаны матрицы смежности неориентированного графа и ориентированного графа, изображенных на рис. 22.1,(а) и 22.2,(а) соответственно. Матрице смежности графа требуется 9(Ъ'з) памяти независимо от количества ребер графа. Обратите внимание на симметричность матрицы смежности на рис. 22.1,(в) относительно главной диагонали. Поскольку граф неориентирован, (и, с) и (с, и) представляют одно и то же ребро, так что матрица смежности неориентированного графа совпадает с транспонированной матрицей смежности, т.е. А = Ат. В ряде приложений это свойство позволяет хранить только элементы матрицы, находящиеся на главной диагонали и выше нее, что позволяет почти в два раза сократить необходимое количество памяти.
Так же, как и представление со списками смежности, представление с матрицами смежности можно использовать для взвешенных графов. Например, если С = (Ъ",Е) — взвешенный граф с весовой функцией и, то вес ш(и,о) ребра (и, о) Е Е хранится в записи в строке и и столбце о матрицы смежности. Если ребро не существует, то в соответствующем элементе матрицы хранится значение нп., хотя для многих приложений удобнее использовать некоторое значение, такое как О или оо.
Хотя список смежности асимптотически как минимум столь же эффективен в плане требуемой памяти, как и матрица смежности, простота последней делает ее предпочтительной при работе с небольшими графами. Кроме того, в случае невзвешенных графов для представления одного ребра достаточно одного бита. что позволяет существенно сэкономить необходимую для представления память 629 Глава 22. Элеиелтариме алгоритмм длл работм с графами Представление атрибутов Большинству алгоритмов для работы с графами требуется поддержка атрибутов для вершин и/или ребер. Мы указываем эти атрибуты с помощью обычных обозначений, таких как о. Ы в случае атрибута д вершины о.
Когда мы указываем ребра как пары вершин, то используем тот же стиль обозначений. Например, если ребра имеют атрибут 1, то этот атрибут для ребра (и, е) обозначается как (и, о).1'. Для представления и понимания алгоритмов такой записи атрибутов вполне достаточно. Реализация атрибутов вершин и ребер в реальных программах — это совершенно другая история. Нет некоторого наилучшего способа хранения атрибутов вершин и ребер и работы с ними. В каждой конкретной ситуации решение, скорее всего, будет зависеть от используемого языка программирования, реализуемого алгоритма и от того, как остальная часть программы использует граф, Если граф представлен с помощью списков смежности, один из вариантов представления атрибутов — применение дополнительных массивов, таких как массив 4[1 ..
])Г]], параллельных массиву Ао21 Если вершины, смежные с и, находятся в А4[и], то то, что мы называем атрибутом и. о', в действительности хранится в элементе массива И[и]. Возможны и многие иные способы реализации атрибутов. Например, в объектно-ориентированном языке программирования атрибуты вершин могут быть представлены как переменные экземпляров в подклассе класса 12егт.ех. Упражнения 22.1.1 Имеется представление ориентированного ~рафа с использованием списков смежности.
Как долго будут вычисляться исходящие степени всех вершин графа? А входящие степени? 22.1.2 Имеется представление с использованием списков смежности полного бинарного дерева с 7 вершинами. Приведите его представление с использованием матрицы смежности (считаем, что вершины пронумерованы от 1 до 7, как в бинарной пирамиде). 22.1.З При транслонировании (папзрозе) ориентированного графа С = (Ъ; Е) мы получаем граф Ст = (Ъ; Ет), где Ег = (,(о, и) ~ 1г х $': (и, о) е Е), т.е. граф Ст представляет собой граф С с обратным направлением ребер.
Опишите эффективный алгоритм транспонирования графа как для представления с использованием списков смежности, так и для матриц смежности. Проанализируйте время работы своих алгоритмов. 22.1.4 Имеется представление мультиграфа С = ()г, Е) с использованием списков смежности. Опишите алгоритм со временем работы 0(Ъ' + Е) для вычисления представления со списками смежности "эквивалентного" неориентированного графа Часть Кя Алгоритмы длл рабааьы с графами 630 С' = (Ъ; Е'), где Е' состоит из ребер из Е, где кратные ребра заменены обычны- ми и удалены ребра-циклы. 22.1.
5 Квидратолг (зцпаге) ориентированного графа С = (1г, Е) является граф Сз = (Ъ;Ез), такой, что (ь, 0) е Ез тогда и только тогда, когда С содержит путь между и и с, состояший не более чем из двух ребер. Опишите эффективный алгоритм вычисления квадрата графа как для представления с использованием списков смежности, так и для матриц смежности. Проанализируйте время работы своих алгоритмов. 22.1.
б При использовании матриц смежности большинство алгоритмов для работы с графами требуют времени Й((гз), но имеются и некоторые исключения. Покажите, что определить, содержит ли граф С всеобщий сток (цпгкегаа( з1п)г), т.е, вершину с входящей степенью, равной ~Ц вЂ” 1, и с исходящей степенью О, можно за время 0(И), если использовать представление графа с помощью матрицы смежности.
22.1.7 Матрицей инцидентности (шок)епсе ша1пх) ориентированного ~рафа без петель С = ((г, Е) является матрица В = (б; ) размером Щ х )Е), такая, что — 1, если ребро з' выходит из вершины з, б;г = 1, если РебРо 1' входит в веРшинУ ь', О в противном случае . Поясните, что представляют собой элементы матричного произведения ВВт, где Вт — транспонированная матрица В. 22.1.б Предположим, что вместо связанного списка каждый элемент массива Аь(1[и] представляет собой хеш-таблицу, содержащую вершины с, для которых (и, с) й Е. Чему равно ожидаемое время определения наличия ребра в графе, если проверка всех ребер выполняется с одинаковой вероятностью. Какие недостатки имеет данная схема? Предложите другие структуры данных для списков ребер, которые позволяют решать поставленную задачу. Имеет ли ваша схема преимущества или недостатки по сравнению с хеш-таблицами? 22.2. Поиск в ширину Поиск в ширину (ЬгеайглкйгзГ зеагсл) представляет собой один из простейших алгоритмов для обхода графа и является основой для многих важных алгоритмов для работы с графами.
Например, алгоритм Прима (Рпш) поиска минимального г'лала 22. Элементарные аягоратмы блл работы с графами 63! остовного дерева (раздел 23.2) или алгоритм Дейкстры (ЕВ1(слуга) поиска кратчайших путей из одной вершины (раздел 24.3) применяют идеи, сходные с идеями, используемыми при поиске в ширину. Пусть задан граф С = (ьг,Е) и выделена исходная вершина (источник, зошсе) и. Алгоритм поиска в ширину систематически обходит все ребра С для "открытия" всех вершин, достижимых из в, вычисляя при этом расстояние (минимальное количество ребер) от в до каждой достижимой из в вершины.
Кроме того, в процессе обхода строится "дерево поиска в ширину" с корнем и, содержащее все достижимые вершины. Для каждой достижимой из л вершины и простой путь в дереве поиска в ширину соответствует "кратчайшему (т.е. содержащему наименьшее количество ребер) пути" от б до и в С, т.е. пути, содержащему наименьшее количество ребер. Алгоритм работает как для ориентированных, так и для неориентированных графов. Поиск в ширину имеет такое название потому, что в процессе обхода мы идем вширь, т.е, перед тем как приступить к поиску вершин на расстоянии ге + 1, выполняется обход всех вершин на расстоянии к. Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными.
Когда вершина впервые открывается (б(зсочегед) в процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить заявленный порядок обхода.' Если (и, и) Е Е и вершина и черного цвета, то вершина и либо серая, либо черная, т.е. все вершины, смежные с черной, уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами.
Поиск в ширину строит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина в. Если в процессе сканирования списка смежности уже открытой вершины и открывается белая вершина и, то вершина и и ребро (и, и) добавляются в дерево. Мы говорим, что и является лредшеслгвенником (ргедесеззог), или родителем (рагепГ), и в дереве поиска вширь. Поскольку вершина может быть открыта не более одного раза, она имеет не более одного родителя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
