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

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

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

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

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


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

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


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


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


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


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

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


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


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




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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


[math]Tree=Tree\cup\bigl\{\{v,w\}\bigr\},[/math]

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


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


[math]Back=Back\cup\bigl\{\{v,w\}\bigr\},[/math]

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


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


[math]F_c=F_c\cup\{Cycle\}.[/math]

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

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


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


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


[math]v_1,\, v_2,\, v_4,\, v_3,\, v_1[/math] и [math]v_0,\, v_1,\, v_2,\, v_4,\, v_3,\, v_0[/math].

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


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


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


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

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

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

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


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


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


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


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


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


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


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


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


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


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


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

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


[math]\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}[/math]
(5.2)

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


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


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




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


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


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


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


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


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


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


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


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


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


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


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


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


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




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

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


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


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

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


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


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


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

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