Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 126
Текст из файла (страница 126)
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Ь. Расстояние от в до вершины и, вычисляемое алгоритмом, хранится в поле Н [и]. Алгоритм использует очередь Я (см. раздел 10.1) для работы с множеством серых вершин: ВРБ(С, в) 1 1ог (для) каждой вершины и Е Ъ'[С] — в г до со1ог[и] ьчн!ти 3 г([и] +- оо 4 я[и] +- ьгП.
5 со1ог[в] — пкА~' б 0[в] < — 0 я[в] — ьгп. Глава 22. Элементарные алгоритмы для работы с графами 615 Г ') л ~д О Ц (ы)'г 1' г г ~ а ГЖ2 ф' 2 2 а В х Ях~, т) Е г ,'(~ (х~ Р а' Х у г 1 а и 1,— Я Гх ~ ~т1 а ) 1 ц Г=т ~у 1 1 а х ) / а ! И Е ,и ЯФ ~ Д Гт а а т Г 0 И и в а г Рис. 22.3. Выполнение процедуры ВРЕ над неорнентнрованным графом 8 Я+-9 9 ЕЖ~Х1ЕСЕЯ, з) 10 ттЬНе Я ф 6 11 Йо и РЕОиЕБЕ(Я) 12 1ог (для) каждой э Е "Цт'1и] 13 йо Ы со1ог~и)) = тти1те 14 11геи со1ог'(п) — Пнду 15 Н(о) — И(и) + 1 16 И 17 Е1ЧО~Е11Е(Д, о) 18 со1ог(и) - ВЬАСК На рис.
22.3 проиллюстрирована работа процедуры ВРБ. Внутри каждой вершины графа и приведено значение И[и), а состояние очереди Я показано на Часть Ч1. Алгоритмы для работы с графами 616 момент начала каждой итерации цикла тт)п1е в строках 10-18. Рядом с элементами очереди показаны расстояния до юрия. Процедура ВРИ работает следующим образом. В строках 1-4 все вершины, за исключением исходной вершины з, окрашиваются в белый цвет, для каждой вершины и полю д [и] присваивается значение оо, а в качестве родителя для каждой вершины устанавливается хп.. В строке 5 исходная вершина а окрашивается в серый цвет, посюльку она рассматривается как открытая в начале процедуры. В строке 6 ее полю д[а] присваивается значение О, а в строке 7 ее родителем становится мп..
В строках 8-9 создается пустая очередь Я, в которую помещается один элемент ж Цикл тт)з11е в строках 10-18 выполняется до тех пор, пока остаются серые вершины (т.е. открытые, но списки смежности которых еще не просмотрены). Инвариант данного цикла выглядит следующим образом: При выполнении проверки в строке 10 очередь Я состоит из множе- ства серых вершин. Хотя мы не намерены использовать этот инвариант для'доказательства корректности алгоритма, легко увидеть, что он выполняется перед первой итерацией и что каждая итерация цикла сохраняет инвариант. Перед первой итерацией единственной серой вершиной и единственной вершиной в очереди Я, является исходная вершина а.
В строке 11 определяется серая вершина и в голове очереди ф которая затем удаляется из очереди. Цикл (ог в строках 12-17 просматривает все вершины о в списке смежности и. Если вершина и белая, значит, она еще не открыта, и алгоритм открывает ее„выполняя строки 14-17. Вершине назначается серый цвет, дистанция и' [о] устанавливается равной о [и] + 1, а в качестве ее родителя указывается вершина и. После этого вершина помещается в хвост очереди Я.
После того как все вершины из списка смежности и просмотрены, вершине и присваивается черный цвет. Инвариант цикла сохраняется, так как все вершины, которые окрашиваются в серый цвет (строка 14), вносятся в очередь (строка 17), а вершина, которая удаляется из очереди (строка 11), окрашивается в черный цвет (строка 18). Результат поиска в ширину может зависеть от порядка просмотра вершин, смежных с данной вершиной, в строке 12.
Дерево поиска в ширину может варьироваться, но расстояния о, вычисленные алгоритмом, не зависят от порядка просмотра (см. упражнение 22.2-4). Анализ Перед тем как рассматривать различные свойства поиска в ширину, начнем с самого простого — оценки времени работы алгоритма для входного графа С = = (К,Е). Мы воспользуемся групповым анализом, описанным в разделе 17.1. Глава 22.
Элементарные алгоритмы для работы с графами 617 После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют О(1) времени, так что общее время операций с очередью составляет О (ьг). Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Так как сумма длин всех списков смежности равна 9 (Е), общее время, необходимое для сканирования списков, равно О (Е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
