XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 50
Текст из файла (страница 50)
Предположим, что после сортировки первым в очереди находится ребро 199, 911 с весом 2. 2 "з о ю о "з о "з 4 ~>з ег Рис. 5.19 б.б. Методы обхода аеряаве Исходный граф изображен на рис. 5.19, а. На рис. 5.19, б проиллюстрирован результат выполнения первого шага алгоритма. На рис. 5.19, в показан результат добавления следующего ребра 1ом еэ) с весом 2 из очереди.
На рис. 5.19, г приведен результат добавления ребра 1вв, е4) с весом 3. Если следующим в очереди ребром будет (ем ве), оно будет отброшено. Дальнейший ход работы алгоритма зависит от того, в каком порядке в очереди размещены ребра 1вэ, гз) и (ез, е4) с весами 4. Любое из них может быть добавлено в множество ребер остовного дерева, и на этом алгоритм закончит работу. На рис. 5.19, д приведено остовное дерево, полученное после добавления ребра 1взз г4). Отметим, что для приведенного графа оба ребра с весом 2 войдут в остовное дерево независимо от порядка их расположения в очереди после сортировки, а ребро (ем ве) не войдет ни в какое остовное дерево наименьшего веса. Можно доказать, что наиболее трудоемким шагом в алгоритме Краскала является сортировка ребер графа по возрастанию весов.
Как мы уже знаем, задачу соршировни и элементов нельзя решить быстрее, чем за время 0(н1обгн). Следова тельно, сложносшь алгорн~има Краскала оценивается числом ОцЩ 1ояэ ~Е~), где ~Е~ — мощность множества ребер графа. Поскольку справедливо неравенство ~Е~ 1ояэ Щ < )Е~Г', то алгоритм Краскала можно считать эффективным. 5.5. Методы систематического обхода вершин графа Важными задачами теории графов являются задача глобального анализа как неориентирвваннмх, так и ориентированных графов. К этим задачам относятся, например, задачи поиска авилов или нонтпуров, вычисление длин ндтгб между парами вершин, перечисление нртиеб с теми или иными свойствами и т.п. Глобальный анализ графа следует отличать от 312 5.
ТЕОРИЯ ГРАФОВ локального, примером которого может служить задача определения множеств предшественников и преемников фиксированной вершины ориентированного графа. Базой для решения многвх задач глобального анализа являются так называемые алгоритмы обхода или поиска. Необходимо уметь обходить все вершины графа таким образом, чтобы каждая вершина была отмечена ровно один раз. Обычно такое „путешествие" по графу сопровождается нумерацией вершин графа в том порядке, в котором они отмечаются, а также определенной „маркировкой" ребер (или дуг) графа. Существуют две основные стратегии таких обходов: поиск в елрбпмд и поиск в шпрпму.
Эти стратегии можно описать так. При поиске в глубину, отправляясь в „путешествие" по гра; фу из некоторой начальной вершины ее, мы действуем следующим образом. Пусть, „путешествуя", мы достигли некоторой вершины е (в начале „путешествия" в = ие). Отмечаем вершину е и просматриваем вершины из ее списка смежностпи Це]. При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем „путешествие" из первой такой вершины ш, действуя как описано вьппе — „ныряем" вглубь, т.е. просматриваем вершины списка смежности Ь[ш] вершины ш, откладывая анализ других элементов Ь(е] как возможных продолжений поиска „на потом".
Если же неотмеченных вершин в Щ нет,то возвращаемся из е в ту вершину, иэ которой мы в нее попали, и продолжаем анализировать список смежности этой вершины. „Путешествие" прекратится в тот момент, когда мы вернемся в начальную вершину ее и либо все вершины будут отмеченными, либо окажется, что неотмеченные вершины есть, но из ве больше никуда пойти нельзя. В последнем случае возможны продолжение поиска из новой вершины или остановка, что определяется конкретной версией алгоритма. 5.5.
Методы обхода аершяя Заметим, что результат поиска в глубину зависит от порядка вершин в списках смежности, представляющих граф, а также от выбора начальной вершины яо. На рис. 5.20 показаны примеры поиска в глубину на неориентированном и ориентированном графах. Рис. 5.20 Рассмотрим неориентированный граф, изображенный на рис. 5.20, а. Списки смежности вершин графа удобно задать КОРтсзКОМШ оО + (01~ оз)э о1 "+ (еаза о2з ЕЗ)э Е2 + (о1з 04)з ЕЗ + (оО> о1~ 04~ о5)з 04 + (02э ЕЗ)з 05 + (Езэ 06~ 07)э Еб + (05)з Е7 "+ (о5). (5.1) Здесь запись еч — 1 (еа,...,еш) означает, что кортеж (еа,...,еш) задает список смежности вершины 01.
Результаты работы алгоритма с использованием приведенных списков смежности проиллюстрированы графически. При поиске отмечаем вершины, присваивая нм номера. Прн зтом каждая новая вершина получает номер, на единицу больший, чем текущая. Вершине ео присвоим номер 1. Номера остаяьных вершин, присвоенные им в процессе поиска, приведены на графе. Ребра, по которым из текущей вершины переходим к новой, изображены более толстыми линиями.
Прокомментируем поиск в глубину в ориентированном графе, изображенном на рис. 5.20,б. Пусть списки смежности 314 5. ТЕОРИЯ ГРАФОВ вершин имеют следующий вид: ео 1(е1 ез) е1 + (е2) 2 + О ез ~ (е1, е4), е4 ~ (е2)~ ео 1(ез~ ее~ е7)~ еб + От е7 1 О „Путешествие" начинается в вершине ео, и ей присваивается номер 1. Первой в списке смежности вершины ео стоит вершина е1. Даем ей номер 2 и продолжаем поиск из этой вершины.
В списке смежности последней только одна вершина е2. Даем ей номер 3 и, так как ее список смежности пуст, возвращаемся в вершину е1. В списке смежности вершины е1 нет других вершин, кроме вершины е2, уже помеченной номером 3, поэтому возвращаемся в вершину ео. Второй элемент списка смежности вершины ео — вершина ез. Эта вершина новая.
Помечаем ее номером 4 и переходим к рассмотрению ее списка смежности. Первая в списке смежности вершина е1 уже получила номер 2. Поэтому переходим в новую вершину е4 и помечаем ее номером 5. Единственный элемент ее списка смежности, вершина е2, уже отмечена. Возвращаемся в вершину ез.
Здесь тоже нет никаких „отложенных продолжений", и мы снова оказываемся в стартовой вершине ео. Все вершины из списка смежности стартовой вершины уже отмечены, т.е. все возможные пути поиска из этой вершины пройдены. Тем не менее в графе остались непосещенные (непронумерованные) вершины. Следующей по исходной нумерации вершин графа является вершина ео. Продолжим поиск из этой вершины и пометим ее номером 6. Первая вершина ее списка смежности — вершина ез — уже отмечена.
Посещаем следующую вершину — вершину ео — и помечаем ее номером 7. Ее список смежности пуст. Возвращаемся в вершину ео. Посещаем последнюю неотмеченную вершину из ее списка смежности — вершину е7 — и помечаем ее номером 8. Поскольку все вершины из списка смежности вершины ео отмечены, поиск в глубину закончен. 315 б.б.
Методы обхода еершвв На рис. 5.20, б более толстыми стрелками изображены дуси, по которым из очередной текущей вершины мы переходили к новой. Рассмотрим теперь поиск в ширину. При поиске в ширину „правила игры" такие: достигнув некоторой вершины е, отмечаем ее. Затем просматриваем ее список смежности Ь[е] и отмечаем все ранее не отмеченные вершины списка (при старте поиска е = ее). После того как отмечены все вершины из Ь[е], вершину е считаем полностью обработанной и продолжаем обработку вершин из списка А[с] по очереди согласно описанным правилам. Именно в обработке сразу всего списка смежности текущей вершины заключается принципиальное отличие поиска в ширину от поиска в глубину: там мы „ныряли" как можно „глубже", а здесь идем с „бреднем", езагребаяа сразу все, что можно.
Поиск в ширину заканчивается, когда все вершины полностью обработаны или продолжение поиска невозможно. Для сравнения возьмем неориентированный и ориентированный графы предыдущего примера и рассмотрим для них поиск в ширину (рис. 5.21). о, Рве. 6.21 Для неориентированного графа (см. рис. 5.21, а) поиск нз стартовой вершины се будем осуществлять так. Стартовой вершине присвоим номер 1. Затем пронумеруем все вершины из списка смежности стартовой вершины в порядке следования 316 5. ТЕОРИЯ ГРАФОВ их в списке. При этом вершина п1 получит номер 2, а вершина ез — номер 3.
Теперь, когда все вершины из списка смежности вершины ев отмечены, перейдем в первую по очереди вершину е1. В ее списке смежности только одна ранее не отмеченная вершина — ез. Присвоим ей номер 4 и перейдем в вершину ез. На этом этапе номер 5 получит вершина е4, а номер 6 — вершина ее. Затем перейдем в вершину ез. Поскольку все вершины из списка смежности вершины ез уже отмечены, перейдем в вершину е4. Здесь также все вершины из списка смежности отмечены, поэтому перейдем в вершину пз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
