Алгоритмы - построение и анализ (1021735), страница 124
Текст из файла (страница 124)
Представление графа С = (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, как в бинарной пирамиде). 22.1-3. При транспоиировааии (1гапзрозе) графа С = (У, Е) мы получаем граф Ст = (У, Ет), где Ет = ((и, и) е У х У: (и,и) е Е), т.е.
граф Ст представляет собой граф С с обратным направлением ребер. Опишите эффективный алгоритм транспонирования графа, как для представления с использованием списков смежности, так и для матриц смежности. Проанализируйте время работы ваших алгоритмов. 22.1-4. Имеется представление мультиграфа С = (У, Е) с использованием списков смежности. Опишите алгоритм со временем работы 0 (У+ Е) для вычисления представления со списками смежности "эквивалентного" неориентированного графа С' = (У, Е'), где Е' состоит из ребер из Е, где кратные ребра заменены обычными и удалены ребра-циклы. 22.1-5. Квадратом (зпиаге) ориентированного графа С = (У, Е) является граф Сз = (У, Е ), такой что (и, ю) Е Е тогда и только тогда, когда для некоторой вершины и е У и (и, и) е Е, и (и, ю) е Е (т.е.
Сз содержит ребро между и и ю, если в С между и и ю имеется путь, состоящий из двух ребер). Опишите эффективный алгоритм вычисления квадрата графа как для представления с использованием списков смежности, так и для матриц смежности. Проанализируйте время работы ваших алгоритмов. Глава 22. Элементарные алгоритмы для работы с графами 613 22.1-6. При использовании матриц смежности большинство алгоритмов для работы с графами требуют времени П (Ъ'з), но имеются и некоторые исключения. Покажите, что определение того, содержит ли граф С всеобщий согок (пп1чегза1 з(пк), т.е. вершину со входящей степенью, равной ٠— 1, и с исходящей степенью О, возможно выполнить за время О (Ъ"), если использовать представление графа при помощи матрицы смежности.
22.1-7. Матрицей инцидеиций (1псЫепсе шагпх) ориентированного графа С = = (1г, Е) является матрица В = (Ьг ) размером 1Ц х 1Е~, такая что если ребро з выходит из вершины 1, если ребро з' входит в вершину г, в противном случае. Поясните, что представляют собой элементы матрицы В Вт, где Вт— транспонированная матрица В. 22.1-8. Предположим, что вместо связанного списка каждый элемент массива Аг(7' [и! представляет собой хеш-таблицу, содержащую вершины е, для которых (и, и) е Е.
Чему равно математическое ожидание времени определения наличия ребра в графе, если проверка всех ребер выполняется с одинаковой вероятностью. Какие недостатки имеет данная схема? Предложите другие структуры данных для списюв ребер, которые позволяют решать поставленную задачу. Имеет ли ваша схема преимущества или недостатки по сравнению с хеш-таблицами? 22.2 Поиск в ширину Поиск в гиирииу (Ьгеаг(гй-бгзг зеагсЬ) представляет собой один из простейших алгоритмов для обхода графа и является основой для многих важных алгоритмов для работы с графами.
Например, алгоритм Прима (Рпш) поиска минимального остовного дерева (раздел 23.2) или алгоритм Дейкстры (1311Ыга) поиска кратчайшего пути из одной вершины (раздел 24.3) используют идеи, сходные с идеями, используемыми при поиске в ширину. Пусть задан граф С = ()г, Е) и выделена исходная (зопгсе) вершина ж Алгоритм поиска в ширину систематически обходит все ребра С для "открытия" всех вершин, достижимых из а, вычисляя при этом расстояние (минимальное количество ребер) от в до каждой достижимой из в вершины. Кроме того, в процессе обхода строится "дерево поиска в ширину" с юрием в, содержащее все достижимые вершины.
Для каждой достижимой из в вершины е путь в дереве поиска в ширину соответствует кратчайшему (т.е. содержащему наименьшее количество 614 Часть Ч1. Алгоритмы для работы с графами ребер) пути от в до и в С. Алгоритм работает как для ориентированных, так и для неориентированных графов. Поиск в ширину имеет такое название потому, что в процессе обхода мы идем вширь, т.е. перед тем как приступить к поиску вершин на расстоянии к+ 1, выполняется обход всех вершин на расстоянии к. Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета.
Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина открывнется (б(зсочегеб) в процессе поиска, она окрашивается. Таким образом, серые и черные вершины— это вершины, которые уже были открыты, но алгоритм поиска в ширину поразному работает с ними, чтобы обеспечить объявленный порядок обхода. Если (и,и) Е Е и вершина и черного цвета, то вершина и либо серая, либо черная, т.е. все вершины, смежные с черной, уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами. Поиск в ширину строит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина в.
Если в процессе сканирования списка смежности уже открытой вершины и открывается белая вершина и, то вершина и и ребро (и, и) добавляются в дерево. Мы говорим, что и является нредшественннкам (ргебесеззог), или родителем (рагепг), и в дереве поиска вширь. Поскольку вершина может быть открыта не более одного раза, она имеет не более одного родителя. Взаимоотношения предков и потомков определяются в дереве поиска в ширину как обычно — если и находится на пути от корня а к вершине и, то и является предком и, а и — потомком и. Приведенная ниже процедура поиска в ширину ВРЯ предполагает, что входной граф С = (1г, Е) представлен при помощи списков смежности.
Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины и е 1' хранится в переменной со1ог [и]„а предшественник— в переменной я [и]. Если предшественника у и нет (например, если и = в или и не открыта), то я [и] = Ы1Ь. Расстояние от в до вершины и, вычисляемое алгоритмом, хранится в поле Н [и]. Алгоритм использует очередь Я (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
