Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Обход по уровням


Обход в глубину

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

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

При реализации алгоритма обхода в глубину используется рекурсивный вызов процедуры.

 

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

Алгоритм обхода вершин графа по уровням приведен на рис. 14.31. В отличие от обхода в глубину, этот алгоритм реализован с использованием очереди. Очередь — это специальный программный механизм, предназначенный для упорядоченного хранения и извлечения данных. При помощи процедуры Enqueue заданный объект помещается в конец очереди, а процедура Dequeue извлекает из начала очереди размещенный там объект. Таким образом, пока идет обработка данных в узлах те­кущего уровня, узлы следующего уровня, связанные ребрами с текущими узлами, помещаются в очередь.

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

<== предыдущая лекция | следующая лекция ==>
Представление и обработка данных в виде графов | Сортировка вставками

Дата добавления: 2014-01-03; Просмотров: 167; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:

  1. Акселератор (не путать с мультипликатором) показывает, на сколько рублей необходимо увеличить инвестиции при увеличении объемов национального производства на один рубль.
  2. Александр П. Попытка модернизации России А. Необходимость реформ.
  3. В ряде случаев для достижения лечебного эффекта необходимо длительное время поддерживать большую концентрацию антитоксина в организме, что достигается повторными его введениями.
  4. Возникновение денег и их виды, необходимость в рыночной экономике.
  5. Вопрос. Необходимость корпоративного налогового менеджмента на предприятии
  6. Все необходимые средства линейных программ.
  7. Гражданско-правовые договоры со сторонними лицами заключаются, прежде всего, в связи с отсутствием необходимых специалистов в организации.
  8. Дефицит необходимого продукта как условие производства прибавочного
  9. Диабетическая кома развивается постепенно. Для спасения больного необходимо доставить в больницу, где ему окажут квалифицированную помощь.
  10. Для защиты приобретателя необходимо наличие всех этих условий.
  11. Для определения оставшейся площади необходимо наложить сетку на фрагмент купюры.
  12. Для определения этого показателя необходим шаровой термометр или термоанемометр ТКА-ПКМ.

studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.