XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 52
Текст из файла (страница 52)
Регистрируя удаляемые из стека вершины, можно после очередного его опустошения распечатать номера вершин, принадлежащих данной компоненте. В ориентированном графе поиск в глубину реализуется во многом аналогично поиску в глубину в неориентированном графе. В этом случае возникает остовный ориентированный лес поиска в глубину, дуги которого — это в точности те дуги, по которым в процессе работы алгоритма переходят от очередной вершины к новой, еще не отмеченной вершнне. Можно показать, что зто максимальный остовный лес исходного графа. Слабыми комионентиами этого глубинного остовного леса будут некоторые ориентиированные деревья: поэтому, используемая далее терминология нз теории деревьев относится к той или иной слабой компоненте глубинного остовного леса.
В ориентированном графе вершинам также присваиваются Р-номера. Но классификация дуг при поиске в глубину в ориентированном графе сложнее по сравнению с аналогичной классификацией ребер при поиске в глубину в неориентированном графе. Различают четыре класса дуг: 1) древесные дуги — каждая такая дуга ведетп от оотиа к сыну в глубинном остовном лесу; 2) прямые дуги — каждая такая дуга ведет от подлинного предка к подлинному иоптомку (но не от отца к сыну) в глубинном остовном лесу; 322 5.
ТЕОРИЯ ГРАФОВ 3) обра~ппые дуеп — от потомков к предкам (включая все петли); 4) поперечные дуги — все дуги, не являющиеся ни древесными, ни прямыми, ни обратными. Следовательно, в результате работы алгоритма будут получены множества 2'гее — древесных дуг, Васй — обратных дуг, гогюагЫ вЂ” прямых дуг, С вЂ” поперечных дуг и массив Р, содержащий Р-номера вершин. В процессе работы алгоритма по сравнению с алгоритмом поиска в глубину в неориентированном графе имеется ряд особенностей.
Так, если очередная вершина ю, извлеченная из списка смежности текущей вершины е, новая, т.е. ю Е ~е, то дуга (е, ю) является древесной. Следует добавить дугу (е, ю) в множество древесных дуг (Тасе = 2Гее 0 ((е, юЦ), сделать вершину ю текущей (е = ю) и начать ее обработку. Если вершина ю не новая (ю ф К~), то дуга (е, ю) будет либо прямой, либо обратной, либо поперечной. Если Р-номер вершины е строго меньше Р-номера вершины ю (Р[е] < Р[ю]), то дуга (е, ю) является прямой.
Добавляем ее в множество прямых дуг Уогюагд (Уогюап1 = гегюап1 0 Ое, юЦ). Если Р-номер вершины е не меньше Р-номера вершины ю (Р[е] ) Р[ю]), необходимо проверить, есть ли в стеке ВТАСК вершина ю. Если вершина ю находится в стеке, то дуга (е, ю) является обратной и ее следует добавить в множество обратных дуг Васй (Вася = Васй0((е, юЦ). Если вершины ю в стеке нет, то дуга является поперечной.
Тогда нужно добавить ее в множество поперечных дуг С (С = С 0((е, юЦ). Далее следует перейти к рассмотрению очередной вершины из списка смежности текущей вершины (если он не пуст). Если стек пуст, но не все вершины ориентированного графа обработаны, поиск продолжают из любой необработанной вершины. В случае ориентированного графа поиск контуров на базе поиска в глубину существенно сложнее, чем в случае неориентированного графа, и здесь он не рассматривается.
Однако 323 3.3. Методы обхода вершин можно доказать следующий критерий бесконтурности ориентированного графа: ориентированный граф является бесконтурным тогда и только тогда, когда при поиске в глубину от некоторой начальной вершины множество обратных дуг оказывается пустым. Заметим также, что для ориентированного графа нет такой простой свюи между числом опустошений стека и числом компонент, как для неориентированного графа. На базе алгоритма поиска в глубину может быть разработан эффективный алгоритм поиска бвкомпоненш в ориентированном графе. Однако здесь мы не будем останавливаться нв задаче поиска бикомпонент, тэк как эта ээдвча обсуждается в рамках общей задачи о путях в графах (см.
5.6). Можно показать, что алгоритм поиска в глубину имеет сложность порядка шах(Я, ~Е~). Пример 5.Т. Проведем поиск в глубину на ориентированном графе, представленом на рис. 5.24. Поиск начнем из вершины ес. Пусть списки смежности вершин имеют следующий вид: ФО -+ (е2~ из~ е1)1 61 "+ (ез)~ е2 + (е4~ ез)т ез -+ (еб), е4 -+ (е1), еб -+ (е1), (5.2) еб "+ (из~ еб)~ е7 ~'(оба еб). Результаты выполнения поиска в глубину представлены на рисунке: около каждой вершины указан ее Р-номер, все дре- 3 с Рис. 6.24 324 Б. ХЕОРИЯ ГРАФОВ весные дуги выделены более толстыми стрелками, а прямые, обратные и поперечные помечены буквами Р, В, С соответственно. Первое опустошение стека происходит после обработки первых пяти вершин (в порядке обхода): ее, ез, е4, ез, е1.
После опустошения поиск продолжается из вершины е7, которой присваивается В-номер 6. (Напомним, что в приведенном вьппе апгоритме после опустошения стека для продолжения поиска выбирается любая из необработанных вершин.) В отличие от алгоритма поиска в глубину, алгоритм поиска в ширину использует не стек, а очередь вершин. Мы дадим здесь вариант поиска в ширину, когда, начиная поиск в некоторой начальной вершине ее, мы останавливаемся при первом же опустошении очереди. Это значит, что некоторые из вершин могут остаться неотмеченными.
Таким образом может быть решена задача распознавания достижимости от заданной вершины. Мы совместим также поиск в ширину с вычислением длины кратчайшего пути от ее до любой вершины графа. Будем предполагать, что вершины графа пронумерованы без пропусков числами от О до И: У = (е;: в =О, Ф~. Поиск в ширину рассматриваем только для ориентированного графа.
Алгоритм поиска в ширину в ориентированном графе Вход. Граф С = (К Я), заданный списками смежности; ее — начальная вершина (не обязательно первый элемент массива лидеров). Выход. Массив М меток вершин, где каждая метка равна длине пути от ее до е. О. Очередь Я положить пустой (Я = И). Все вершины пометить как недостижимые из вершины ее, присваивая элементам массива М значение +ос (М(е;] = +оо, ~ = 1, Л). 5.5. Методы обхода вершил 325 Стартовую вершину ео пометить номером О, т.е. длину пути от стартовой вершины ео до самой себя положить равной 0 (М[ео] = О).
Поместить вершину ее в очередь Я. Перейти на шаг 1. 1. Если очередь Я не пуста (Я ф И), то из „головы" очереди извлечь (с удалением из очереди) вершину и и перейти на шаг 2. Если очередь пуста, перейти на шаг 3. 2. Если список смежности Ь(п) вершины п пуст, вернуться на шаг 1. Если список смежности Ци) вершины п не пуст, для каждой вершины ш из списка смежности, где М[ш] = +оо, т.е.
вершины, которую еще не посещали, положить длину пути из стартовой вершины ее до вершины и равной длине пути от ее до вершины и плюс одна дуга (М[ю] = М[в] + 1), т.е. отметить вершину ю и поместить ее в очередь Я. После просмотра всех вершин списка смежности Ци) вернуться на шаг 1. 3. Распечатать массив М. Закончить работу. Алгоритм поиска в ширину может быть дополнен процедурой „обратного хода", определяющей номера вершин, лежащих на кратчайшем пути из вершины ео в данную вершину в Для этого необходимо завести массив РЯ размера [т'], каждый элемент РЩи~~ которого содержит номер той вершины, из которой бь|л осуществлен переход в вершину и при ее пометке. Если вершина и находится в списке смежности Цп) вершины и, заполнение элемента массива РНш] происходит при изменении метки вершины ш М[ю] с +ос на единицу.
При этом в элементе РЯБ] сохраняется номер вершины и (РЦш] = в). Для начальной вершины РЯие] можно положить равным О, в предположении, что начальнал вершина ее имеет номер 0 и остальные вершины пронумерованы от 1 до Ж. Сложность рассмотренного алгоритма поиска в ширину, известного под названием „Алгоритм волнового фронта", составляет 0(шах(Щ, ]Е])).
326 б. ТЕОРИЯ ГРАФОВ Пример 5.8. На рис. 5.25 дан пример работы алгоритма волнового фронта (при поиске из вершины ив) для ориентированного графа, юобрвженного нв рис. 5.24. Списки смежности ориентированного графа имеют вид (5.2). Рис. 6.25 Около каждой вершины и; поставлена метка М(и;), которую получает вершина при поиске в ширину. Выделены дуги, составляющие кратчайшие пути из вершины ие в остальные.
Отметим, что вершины ов, ив, и и7 не достижимы из ио и их начальные метки +со остались без юменения. При рассмотренном ходе алгоритма массив РН будет содержать следующие номера вершин: РН~ие) = О, РН~р11 = О, Руиз) = О, Рйрь) = О, Рйр4) = 2. Для остальных вершин соответствующие значения не опредепены, поскольку они не „посещались". Используя массив РН, восстановим кратчайший путь из вершины ев в вершину и4. Поскольку РН1о4) = 2, в РН1из] = О, искомый путь есть ив, из, и4. 5.6. Задача о путях во взвешенных ориентированных графах Среди задач анализа оривншированнмя графов весьма важны следующие задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
