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

Программная реализация поиска в графе в глубину

Читайте также:
  1. АКТУАЛЬНОСТЬ ГЛОБАЛЬНОГО ВИДЕНИЯ: В ПОИСКАХ УТРАЧЕННОГО БУДУЩЕГО
  2. Алгоритм поиска в ширину
  3. Алгоритм поиска литературы в электронном каталоге
  4. Алгоритм поиска литературы и др. документов
  5. Аппаратная реализация
  6. Аппаратная реализация
  7. Аппаратная реализация

Поиск в глубину

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

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

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

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная.

Шаг 2. Для последней помеченной как посещенная вершины выбирается смежная вершина, являющаяся первой помеченной как не посещенная, и ей присваивается значение посещенная. Если таких вершин нет, то берется предыдущая помеченная вершина.

Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные.

Программная реализация поиска в графе в глубину

Простой неориентированный невзвешенный граф задан матрицей смежности A(n х n), где n – количество вершин графа. Поиск начинается с некоторой фиксированной вершины v. Рассматривается вершина u, смежная с v. Она выбирается. Процесс повторяется с вершиной u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, когда это вершина v, процесс просмотра закончен. Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:

Nnew: array[1..N] of boolean.

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


Дата добавления: 2015-10-13; просмотров: 117 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Когда я ищу счастье, я теряю его. Когда я прекращаю поиски и отдаю себя тому, где я нахожусь, я обретаю его.| Алгоритм поиска в ширину

mybiblioteka.su - 2015-2024 год. (0.006 сек.)