Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Обходы графа в глубину и в ширину

Читайте также:
  1. Архив села Михайловского / [Издание графа С.Д. Шереметева]: Т. 1-2. СПб., 1898-1912.
  2. Виды разверток электронного осциллографа
  3. Виды разверток, применяемых в осциллографах
  4. ГРАФА 15.21
  5. Зірки» кінематографа Марлен Дитріх, Грета Гарбо, Бетт Дейвіс. Головні спільні риси їх творчості
  6. Зірки» кінематографа Марлен Дитріх, Грета Гарбо, Бетт Дейвіс. Головні спільні риси їх творчості.
  7. Информация, содержащаяся в графах 4 и 22 CMR должна быть идентична.
  8. Использование теории архетипов в массовой коммуникации (на примере кинематографа).
  9. Матрица инцидентности (орин. Графа ) Матрица смежности
  10. Находим (интерполированием) глубину зоны заражения первичным облаком

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

Например, используя рекурсивную процедуру, линейный по временной сложности алгоритм обхода графа G в глубину можно записать следующим образом:

procedure ОБХОД-В-ГЛУБИНУ(р: вершина);
begin
Посетить вершину р;
for all q from множества вершин, смежных с р do
if q еще не посещалась then ОБХОД-В-ГЛУБИНУ(q) end
end
end;
begin
for all р from множества вершин G do
if р еще не посещалась then ОБХОД-В-ГЛУБИНУ(р) end
end
end.

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

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

Нерекурсивный вариант алгоритма обхода графа G в глубину может иметь следующий вид:

procedure ОБХОД-В-ГЛУБИНУ-1(р: вершина);
begin
Посетить вершину р и поместить ее в пустой стек S;
while Стек S непуст do
Пусть р – вершина, находящаяся на верхушке стека S;
if у р есть непосещенные смежные вершины then
Пусть q – непосещенная вершина, смежная вершине р;
Пройти по ребру (р, q), посетить вершину q и поместить ее в стек S
else Удалить вершину р из стека S
end
end
end;

Рис. 21. Граф и его обход в глубину

 

Обход в ширину связного графа предполагает рассмотрение всех его вершин в порядке возрастания расстояния от некоторой вершины, с которой начался данный обход графа. Например, в результате обхода графа G (рис. 21) в ширину возможен следующий порядок посещения вершин: C,A,B,D,H,K,L,E,F,G.

Следующий алгоритм позволяет осуществить обход в ширину любого связного графа G:

procedure ОБХОД-В-ШИРИНУ(р: вершина);
begin
Поместить вершину р в пустую очередь O;
while очередь O не пуста do
Взять первую вершину р из очереди O;
if р еще не посещалась then
Посетить вершину р и поместить в очередь O все вершины, смежные с р
end
end
end;

Контрольные вопросы




Дата добавления: 2014-12-18; просмотров: 39 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав