Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Алгоритмы поиска в глубину и ширину в графах

Алгоритмы поиска в глубину и ширину в графах


Одним из способов построения максимального остовного леса может служить поиск в глубину. Именно при поиске в глубину всякое ребро, по которому из текущей вершины мы попадаем в неотмеченную ранее вершину, будет древесным. Каждое ребро, не являющееся древесным, будет обратным. Максимальный остовный лес, находимый с помощью алгоритма поиска в глубину, называют остовным лесом поиска в глубину или глубинным остовным лесом.


Заметим, что классификация ребер зависит от хода работы алгоритма, который определяется стартовой вершиной и расположением вершин в списках смежности.


Таким образом, алгоритм поиска в глубину в неориентированном графе может быть использован для вычисления множества фундаментальных циклов графа, т.е. решения одной из задач глобального анализа.


Граф с выделенным максимальным остовным лесом

Отметим, что не всякий максимальный остовный лес может быть получен с помощью алгоритма поиска в глубину. Например, для графа, изображенного на рис. 5.23, выделенный максимальный остовный лес нельзя получить при поиске в глубину, из какой бы вершины мы не начинали поиск.


Для организации работы алгоритма поиска в глубину используется способ хранения данных, называемый стеком. Элементы в стеке упорядочиваются в порядке поступления. В стек можно добавлять новые элементы и из него можно извлекать элементы. При этом доступен только последний добавленный элемент — вершина стека, чем и определяется режим работы стека (последним пришел — первым ушел). Образно стек можно представить в виде стопки тарелок. Из стопки можно взять только верхнюю тарелку и только наверх можно добавить новую. Обычно стек реализуется в виде списка.


В алгоритме поиска в глубину используется стек вершин. Мы будем считать, что из стека можно считывать информацию без изменения его содержимого, но в том порядке, в каком ее удаляли бы из стека. Указанная операция считывания понадобится нам для поиска фундаментальных циклов.




Алгоритм поиска в глубину


Вход. Граф G=(V,E), заданный списками смежности.


Выход. Множества Tree древесных и Back обратных ребер соответственно; множество F_c фундаментальных циклов, массив D, содержащий D-номера вершин.


0. Просмотреть массив лидеров и сформировать множество V_0 вершин графа. Это множество используется для хранения новых (не обработанных алгоритмом) вершин. В ходе работы алгоритма обработанные вершины будут удаляться из этого множества.


В процессе работы алгоритма для каждой вершины v необходимо знать, какие вершины из ее списка смежности L[v] обработаны на предыдущих шагах работы алгоритма. Для этого формируется массив L_p размера |V_0|, в котором хранятся номера первых еще не обработанных алгоритмом вершин списка смежности L[v] каждой вершины {v}. Первоначально все элементы массива L_p полагают равными 1.


Стек вершин STACK и список вершин фундаментального цикла Cycle положить пустыми (STACK=\varnothing,~Cycle=\varnothing).


Множества Tree древесных ребер, Back обратных ребер и F_c фундаментальных циклов положить пустыми (Tree=\varnothing,~ Back=\varnothing, F_c=\varnothing). Массив D-номеров D обнулить.


Задать начальную вершину для поиска (v=v_0). (Обычно это первая вершина массива лидеров.) Счетчик D-номеров вершин count положить равным 1 (count=1).


1. Если множество V_0 не пусто (V_0\ne\varnothing), перейти на шаг 2, если иначе — на шаг 8 (выход).


2. Если стек пуст (STACK=\varnothing) и алгоритм стартует из вершины v_0 (count=1), то перейти на шаг 3, если иначе, то выбрать из множества V_0 произвольную вершину, из которой поиск в глубину будет продолжен (v=u,\, u\in V_0), и перейти на шаг 3.


3. Поместить текущую вершину {v} в стек STACK. Присвоить вершине {v} D-номер (D[v]=count). Увеличить счетчик D-номеров на 1 (count=count+1). Удалить вершину {v} из множества V_0 новых вершин. Перейти на шаг 4.


4. Проверить по элементу L_p[v], что не достигнут конец списка смежности L[v] текущей вершины {v}. Если в списке смежности есть еще не обработанные вершины, получить из списка смежности очередную вершину w, увеличить L_p[v] на 1 и перейти на шаг 6.


Если список смежности L[v] вершины v обработан полностью, удалить вершину {v} из стека STACK и перейти на шаг 5.


5. Если стек STACK пуст, вернуться на шаг 1, если иначе, то в качестве текущей вершины {v} взять вершину, находящуюся в вершине стека, и перейти на шаг 4.


6. Если вершина w новая (w\in V_0), то добавить ребро \{v,w\} в множество древесных ребер


Tree=Tree\cup\bigl\{\{v,w\}\bigr\},

сделать вершину w текущей (v=w) и вернуться на шаг 3. Если вершина w не новая (w\notin V_0), то перейти на шаг 7.


7. Если ребра \{v,w\} нет среди древесных (\{v,e\}\notin Tree), поместить ребро в список обратных ребер


Back=Back\cup\bigl\{\{v,w\}\bigr\},

Поместить вершину w в список Cycle. Читать содержимое стека STACK, начиная с вершины стека, до появления вершины w и помещать в список Cycle (включая вершину w), т.е. формировать фундаментальный цикл, соответствующий обратному ребру \{v,w\}.


Добавить список Cycle в множество фундаментальных циклов F_c


F_c=F_c\cup\{Cycle\}.

Список Cycle положить пустым (Cycle=\varnothing).

Вернуться на шаг 4.


8. Закончить работу.


Пусть для неориентированного графа, изображенного на рис. 5.20,а, списки смежности имеют вид (5.1). При выполнении поиска в глубину выделенные ребра являются древесными, остальные — обратными. Около каждой вершины указан присвоенный ей D-номер. Фундаментальные циклы — в порядке их нахождения — таковы:


v_1,\, v_2,\, v_4,\, v_3,\, v_1 и v_0,\, v_1,\, v_2,\, v_4,\, v_3,\, v_0.

Поиск в глубину в неориентированном графе можно использовать и для нахождения числа его компонент. Очевидно, что это число равно числу опустошений стека от начала до конца поиска в глубину. Регистрируя удаляемые из стека вершины, можно после очередного его опустошения распечатать номера вершин, принадлежащих данной компоненте.


В ориентированном графе поиск в глубину реализуется во многом аналогично поиску в глубину в неориентированном графе. В этом случае возникает остовный ориентированный лес поиска в глубину, дуги которого — это в точности те дуги, по которым в процессе работы алгоритма переходят от очередной вершины к новой, еще не отмеченной вершине. Можно показать, что это максимальный остовный лес исходного графа.


Слабыми компонентами этого глубинного остовного леса будут некоторые ориентированные деревья: поэтому, используемая далее терминология из теории деревьев относится к той или иной слабой компоненте глубинного остовного леса. В ориентированном графе вершинам также присваиваются D-номера. Но классификация дуг при поиске в глубину в ориентированном графе сложнее по сравнению с аналогичной классификацией ребер при поиске в глубину в неориентированном графе. Различают четыре класса дуг:


1) древесные дуги — каждая такая дуга ведет от отца к сыну в глубинном остовном лесу;

2) прямые дуги — каждая такая дуга ведет от подлинного предка к подлинному потомку (но не от отца к сыну) в глубинном остовном лесу;

3) обратные дуги — от потомков к предкам (включая все петли);

4) поперечные дуги — все дуги, не являющиеся ни древесными, ни прямыми, ни обратными.


Следовательно, в результате работы алгоритма будут получены множества Tree — древесных дуг, Back — обратных дуг, Forward — прямых дуг, C — поперечных дуг и массив D, содержащий D-номера вершин.


В процессе работы алгоритма по сравнению с алгоритмом поиска в глубину в неориентированном графе имеется ряд особенностей. Так, если очередная вершина w, извлеченная из списка смежности текущей вершины {v}, новая, т.е. w\in V_0, то дуга (v,w) является древесной. Следует добавить дугу (v,w) в множество древесных дуг Tree=Tree\cup\{(v,w)\}, сделать вершину w текущей (v=w) и начать ее обработку.


Если вершина w не новая (w\notin V_0), то дуга (v, w) будет либо прямой, либо обратной, либо поперечной.


Если D-номер вершины v строго меньше D-номера вершины w (D[v]<D[w]), то дуга (v,w) является прямой. Добавляем ее в множество прямых дуг Forward (Forward=Forward\cup\{(v,w)\}).


Если D-номер вершины {v} не меньше D-номера вершины w~(D[v]\geqslant D[w]), необходимо проверить, есть ли в стеке STACK вершина w. Если вершина w находится в стеке, то дуга (v,w) является обратной и ее следует добавить в множество обратных дуг Back (Back= Back\cup\{(v,w)\}). Если вершины w в стеке нет, то дуга является поперечной. Тогда нужно добавить ее в множество поперечных дуг C~(C=C\cup\{(v,w)\}). Далее следует перейти к рассмотрению очередной вершины из списка смежности текущей вершины (если он не пуст).


Если стек пуст, но не все вершины ориентированного графа обработаны, поиск продолжают из любой необработанной вершины.


В случае ориентированного графа поиск контуров на базе поиска в глубину существенно сложнее, чем в случае неориентированного графа, и здесь он не рассматривается. Однако можно доказать следующий критерии бесконтурности ориентированного графа: ориентированный граф является бесконтурным тогда и только тогда, когда при поиске в глубину от некоторой начальной вершины множество обратных дуг оказывается пустым.


Заметим также, что для ориентированного графа нет такой простой связи между числом опустошений стека и числом компонент, как для неориентированного графа.


На базе алгоритма поиска в глубину может быть разработан эффективный алгоритм поиска бикомпонент в ориентированном графе. Однако здесь мы не будем останавливаться на задаче поиска бикомпонент, так как эта задача обсуждается в рамках общей задачи о путях в графах.


Можно показать, что алгоритм поиска в глубину имеет сложность порядка \max(|V|,|E|).


Поиск в глубину на ориентированном графе

Пример 5.7. Проведем поиск в глубину на ориентированном графе, представленном на рис. 5.24. Поиск начнем из вершены v_0. Пусть списки смежности вершин имеют следующий вид:


\begin{cases}v_0\to(v_2, v_3, v_1),\quad v_1\to(v_3),\quad v_2\to(v_4, v_3),\\ v_3\to(v_4),\quad v_4\to(v_1),\quad v_5\to(v_1),\\ v_6\to(v_3, v_5),\quad v_7\to(v_5, v_6). \end{cases}
(5.2)

Результаты выполнения поиска в глубину представлены на рисунке: около каждой вершины указан ее D-номер, все древесные дуги выделены более толстыми стрелками, а прямые, обратные и поперечные помечены буквами F,\,B,\,C соответственно.


Первое опустошение стека происходит после обработки первых пяти вершин (в порядке обхода): v_0, v_2, v_4, v_3, v_1.


После опустошения поиск продолжается из вершины v_7, которой присваивается D-номер 6. (Напомним, что в приведенном выше алгоритме после опустошения стека для продолжения поиска выбирается любая из необработанных вершин.)




Алгоритм поиска в ширину в ориентированном графе


В отличие от алгоритма поиска в глубину, алгоритм поиска в ширину использует не стек, а очередь вершин. Мы дадим здесь вариант поиска в ширину, когда, начиная поиск в некоторой начальной вершине v_0, мы останавливаемся при первом же опустошении очереди. Это значит, что некоторые из вершин могут остаться неотмеченными. Таким образом может быть решена задача распознавания достижимости от заданной вершины. Мы совместим также поиск в ширину с вычислением длины кратчайшего пути от v_0 до любой вершины графа. Будем предполагать, что вершины графа пронумерованы без пропусков числами от 0 до N\colon\, \{v_i\colon\, i=\overline{0,N}\}.


Поиск в ширину рассматриваем только для ориентированного графа.


Вход. Граф G=(V,E), заданный списками смежности; v_0 — начальная вершина (не обязательно первый элемент массива лидеров).


Выход. Массив M меток вершин, где каждая метка равна длине пути от v_0 до {v}.


0. Очередь Q положить пустой (Q=\varnothing). Все вершины пометить как недостижимые из вершины v_0, присваивая элементам массива M значение +\infty~(M[v_i]=+\infty,~i=\overline{1,N}).


Стартовую вершину v_0 пометить номером 0, т.е. длину пути от стартовой вершины v_0 до самой себя положить равной 0 (M[v_0]=0). Поместить вершину v_0 в очередь Q. Перейти на шаг 1.


1. Если очередь Q не пуста (Q\ne\varnothing), то из "головы" очереди извлечь (с удалением из очереди) вершину u и перейти на шаг 2. Если очередь пуста, перейти на шаг 3.


2. Если список смежности L(u) вершины u пуст, вернуться на шаг 1.


Если список смежности L(u) вершины и не пуст, для каждой вершины w из списка смежности, где M[w]=+\infty, т.е. вершины, которую еще не посещали, положить длину пути из стартовой вершины v_0 до вершины w равной длине пути от v_0 до вершины u плюс одна дуга (L[w]=M[{u}]+1), т.е. отметить вершину w и поместить ее в очередь Q. После просмотра всех вершин списка смежности L(u) вернуться на шаг 1.


3. Распечатать массив M. Закончить работу.


Алгоритм поиска в ширину может быть дополнен процедурой "обратного хода", определяющей номера вершин, лежащих на кратчайшем пути из вершины v_0 в данную вершину u. Для этого необходимо завести массив PR размера |V|, каждый элемент PR[w] которого содержит номер той вершины, из которой был осуществлен переход в вершину w при ее пометке.


Если вершина w находится в списке смежности L(u) вершины u, заполнение элемента массива PR[w] происходит при изменении метки вершины w~M[w] с +\infty на единицу. При этом в элементе PR[w] сохраняется номер вершины и (PR[w]=u). Для начальной вершины PR[v_0] можно положить равным 0, в предположении, что начальная вершина v_0 имеет номер 0 и остальные вершины пронумерованы от 1 до N.


Сложность рассмотренного алгоритма поиска в ширину, известного под названием "Алгоритм волнового фронта", составляет O(\max(|V|,|E|)).




Пример работы алгоритма волнового фронта (при поиске из вершины v0)

Пример 5.8. На рис. 5.25 дан пример работы алгоритма волнового фронта (при поиске из вершины v_0) для ориентированного графа, изображенного на рис. 5.24. Списки смежности ориентированного графа имеют вид (5.2).


Около каждой вершины v_i поставлена метка M[v_i], которую получает вершина при поиске в ширину. Выделены дуги, составляющие кратчайшие пути из вершины v_0 в остальные. Отметим, что вершины v_5,\,v_6 и v_7 не достижимы из v_0 и их начальные метки +\infty остались без изменения. При рассмотренном ходе алгоритма массив PR будет содержать следующие номера вершин:


PR[v_0]=0,\quad PR[v_1]=0,\quad PR[v_2]=0,\quad PR[v_3]=0,\quad PR[v_4]=2.

Для остальных вершин соответствующие значения не определены, поскольку они не "посещались".


Используя массив PR, восстановим кратчайший путь из вершины v_0 в вершину v_4. Поскольку PR[v_4]=2, a PR[v_2]=0, искомый путь есть v_0,v_2,v_4.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved