 |
|
Математика : Графы.
Поиск вглубь и вширь. Обходы графа.
Для начала пусть дерево G задано множеством вершин V ( корневая вершина v0 ), дуг - E и Г(v,-) - перечнем потомков вершины v из V.
Обход (пока)дерева вширь (сначала уровень 0, затем 1, и т.д.)
будет идти так 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8, если дерево - такое, как на рис.1
уровень:
0 | 0=v0
| /|\
| / | \
| / | \
1 | 1 2 3
| /| |\
| / | | \
2 |4 5 6 7
| \
| \
3 | 8
рис.1.
Он потребует использования очереди QUEUE
---------¬ --------------------------¬
--->¦v=>QUEUE ¦-->¦WHILE QUEUE # ПУСТО DO ¦-------->
---------- ----------+----------------
---------v--------¬ ¦
¦ w<=QUEUE ¦ ¦
¦ USE(w) ¦>--
¦ Г(w,-) => QUEUE ¦
-------------------
Г(w,-) => QUEUE - запись в очередь всего содержимого Г(w,-)
Обход вершин произвольного графа G = { V, E } отличается от обхода дерева лишь тем, что необходимо устранить дублирующее попадание в пройденную вершину. Для этого вводится пометка вершин NEW[V]= 1*TRUE, в стек или очередь заносятся только вершины, помеченные TRUE, при этом их пометка заменяется на FALSE. Следует помнить, что граф может оказаться не связным или некоторые вершины могут быть недостижимы из исходной v0.
Чтобы преодолеть эти проблемы, достаточно организовать просмотр начиная с любой ранее не пройденной вершины.
Алгоритм поиска вглубь на произвольном графе имеет вид:
-------------------¬ ------------------¬
---->¦ FOR v из V DO ¦--------->¦ FOR v из V DO ¦---->
-------------------- -------------------
¦ ¦ ¦ ¦
------v------¬ ¦ -----v-------¬ ¦
¦NEW[V]:=TRUE¦-> ¦ WALK(v) ¦->
-------------- --------------
где рекурсивная процедура WALK соответствует блок-схеме:
--------------¬ ---------------------¬
----->¦ USE(v) ¦---->¦FOR w из Г(v,-) DO ¦----->
¦NEW[V]:=FALSE ¦ ----------------------
--------------- ¦ ¦
-----v--¬нет ¦
¦ NEW[w] ¦--->¦
--------- ¦
¦ да ¦
-----v---¬ ¦
¦ WALK(w) ¦->--
----------
Сложность этого алгоритма О(m+n), где m=||V||, n=||E||.
Достоинства метода:
1. Каждая дуга графа анализируется только один раз.
2. Алгоритм решения задачи легко погружается в этот метод.
Применение алгоритма:
- определение компонент связности графа за О(m+n) операций
- при противоположной пометке вершин алгоритм позволяет определять
наличие контура в графе.
Алгоритм поиска вширь из вершины v0 на произвольном графе имеет вид /первоначально NEW[V] = 1*TRUE/:
----------¬ --------------------------¬
--->¦v0=>QUEUE ¦------>¦WHILE QUEUE # ПУСТО DO ¦-------->
¦NEW[v0]= ¦ -----------+---------------
¦ FALSE ¦ ------------v-------¬ ¦
----------- ¦ v =< QUEUE; USE(v) ¦ ¦
¦ FOR w из Г(v,-) DO ¦>-
-------+-----------+--
------v--¬ нет ¦
¦ NEW[w] ¦------>¦
------+--- да ¦
------v------¬ ¦
¦NEW[w]=FALSE ¦ ¦
¦ w => STACK ¦->--
--------------
Применение алгоритма: - поиск кратчайшего пути на графе (выхода из лабиринта)
Пример использования стратегии "разделяй и властвуй" MINMAX(S) -
одновременный поиск наибольшего и наименьшего значений на множестве
S. Вспомогательные процедуры:
MIN_MAX(min,max,s1,s2) - используя одно сравнение
находит наименьшее min и наибольшее -
max значение среди S={s1,s2} - одного
или двух элементов линейно упорядоченного
множества (например, чисел) s1 и s2.
FMAX(max,s1,s2) - находит наибольшее max,
FMIN(min,s1,s2) - наименьшее min среди s1,s2.
S -> S1 + S2 - эффективная процедура деления множества
S на два примерно равных S1, S2.
Исходные данные - множество S исходных значений (к примеру
вектор S[1:n])
MINMAX(S,min,max)
----------------¬
¦ || S || <= 2 ¦
--+-----------+--
¦ -------¬
------------v---------¬ ----v------------------¬
¦ S -> S1 + S2 ¦ ¦MIN_MAX(min,max,s1,s2)¦
¦ MINMAX(S1,min1,max1)¦ ----+-------------------
¦ MINMAX(S2,min2,max2)¦ ¦
¦ FMIN(min,min1,min2) ¦ ¦
¦ FMAX(max,max1,max2) ¦ ¦
-------------+--------- ¦
¦ -----v--¬
----------->-¦ RETURN ¦-->
---------
Расчет трудоемкости алгоритма. Пусть T(n) - требуемое коли-
чество сравнений для поиска наибольшего и наименьшего значений
среди n чисел. Тогда Т(n) определяется следующим соотношением:
{ 1, n <= 2
T(n) = {
{ 2 T(n/2)+2, n > 2.
Решение соотношения: T(n) = 3/2*n - 2 - трудоемкость алгоритма.
В случае рекуррентного соотношения
{ b, n <= n1
T(n) = {
{ a*T(n/c)+b, n > n1.
его решение имеет следующую асимптотику:
{ O(n), a < c,
T(n) = { O(n*log(n), a = c,
{ O(n**log (a)), a > c.
c
Вверх по странице, к оглавлению и навигации.