Студопедия

КАТЕГОРИИ:

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



Алгоритмы прохождения графа.




Читайте также:
  1. II. Порядок прохождения испытания
  2. Административно-правовой статус государственных служащих и порядок прохождения ими службы
  3. Алгоритмы
  4. Алгоритмы внутренней сортировки. Элементарные методы сортировки
  5. Алгоритмы заливки замкнутых областей.
  6. Алгоритмы маршрутизации в сетях.
  7. Алгоритмы разгона и торможения. Сравнительная оценка алгоритмов. Примеры.
  8. Алгоритмы сжатия без потерь - кодирование длин серий (RLE), алгоритм Лемпеля-Зива-Велча (LZW), форматы GIF и PNG.
  9. Алгоритмы сжатия файлов без потерь

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

Имеем граф G = (X, U), X = {x1, x2,…, xn}. Каждое прохождение можно рассматривать как определенную последовательность. Максимальное число прохождений (перестановок) – n!.

Алгоритм прохождения графа в глубину:

 

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

Определимсписки смежности для каждой вершины графа G:

1:2, 3, 5 2:1, 3, 4 3:1, 2, 4, 5 4: 2, 3 5: 1,3

               
     
     
 


t: 1, 2, 3, 4, 5

 

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

Для каждого выбора начальной вершины в связном графе может быть получено единственное прохождение. Если граф представляет собой объединение компонент: и | x i | = n i , то количество прохождений такого несвязного графа: n 1 × n 2 × … × n р ( i = 1, 2,…, p).

Пусть граф G = (X, U) задан структурой смежности < М(x 1), М(x 2),…, М(x n)>. Определим Num(x) как массив для регистрации посещений вершин (Num(x)=1, если вершина не посещалась; Num(x)=0, если вершина посещалась). Тогда алгоритм прохождения графа в глубину будет выглядеть так:

" x Î X выполнить Num(x)=1;

" x Î X выполнить: если Num(x)=1, то D(x);

Процедура D(x);

начало

R(V);

Num(V)=0;

" t Î M(V) выполнить: если Num(t)=1, то D(t);

конец;

Алгоритм прохождения графа в ширину:

Определимсписки смежности для каждой вершины графа G:



1:2, 3, 5 2:1, 3, 4 3:1, 2, 4, 5 4: 2, 3 5: 1,3

t: 1, 2, 3, 4, 5 (для выбранной вершины переписываем весь список смежности).

Выберем начальную вершину x н. Первые элементы искомой перестановки t являются элементами смежного списка вершины x н, т.е. M(x н). Обозначим список смежности следующим образом: M(x н) = {(w1, xн), (w2, xн),…,(wk, xн)}. Следующими элементами перестановки будут те элементы их M(w1), которые отсутствуют в формируемой перестановке t. Затем, берем все элементы из M(w2), и т.д. обход прекращается, когда все вершины, достижимые из x н, будут содержаться в t (wi Î X, i=1, 2,…, k).

 


Дата добавления: 2015-04-18; просмотров: 29; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.004 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты