Алгоритмы на графах

В отличии от алгоритма поиска в глубину, алгоритм поиска в ширину используется не стек, а очередь вершин. Мы дадим здесь вариант поиска в ширину, когда, начиная поиск в некоторой начальной вершине v0, мы останавливаемся при первом же опустошении очереди. Это значит, что некоторые из вершин могут остаться неотмеченными. Таким образом может быть решена задача распознавания достижимости от заданной вершины. Мы совместим также поиск в ширину с вычислением длины кратчайшего пути от  v0  до любой вершины графа. Будем предполагать, что вершины графа пронумерованы без пропусков числами от 0 до N: V ={ vi : i = 0,N}.

Рассмотрим алгоритм поиска в ширину в ориентированном графе:

Вход.   Граф  G = (V,E),  заданный списками смежности;

v0  - начальная вершина (не обязательно первый элемент массива лидеров)

Выход.  Массив  М  меток  вершин, где каждая метка равна  длине пути от  v0  до  v .

 0.  Очередь Q  положить  пустой  (Q = ø). Все вершины пометить как недостижимые из вершины   v0, присваивая элементам массива М значение  + ∞(М[vi] = + ∞,i = 1, N). Стартовую вершину v0   пометить номером 0, т.е. длину пути от стартовой вершины v0  до самой себя положить равной 0                   ( М[v0]=0 ). Поместить вершину v0 в очередь Q. Перейти на шаг 1.

1 Если очередь Q не пуста (Q≠ø), то из « головы» очереди извлечь (с удалением из очереди) вершину u и перейти на шаг 2. Если очередь пуста, перейти на шаг 3.

2 Если список смежности L(u)  вершины u  пуст, вернуться на шаг 1.  Если список смежности L(u) вершины u не пуст, для каждой вершины w  из списка смежности, где М[w] = +∞, т.е. вершины, которую еще не посещали, положить длину пути из стартовой вершины v0 до вершины w равной длине пути от v0  до  вершины u плюс одна дуга  (М[w] = M[u]+1) , т.е. отметить вершину w  и поместить ее в очередь Q. После просмотра всех вершин списка смежности L(u) вернуться на  шаг 1.

3. Распечатать массив М. Закончить работу. Алгоритм поиска в ширину может быть дополнен процедурой «обратного хода», определяющей номера вершин, лежащих на кратчайшем пути из вершины v0  в данную вершину u. Для этого необходимо завести массив PR  размера │V│ , каждый  элемент PR[w]  которого содержит номер той вершины, из которой был осуществлен переход в вершину w  при ее пометке.   Если вершина w находится в списке смежности L(u) вершины u, заполнение элемента массива PR[w]  происходит при изменении метки вершины w M[w]c +∞ на единицу. При этом в элементе PR[w]  сохраняется номер вершины u (PR[w] = u). Для начальной вершины PR[v0]  можно положить равным 0, в предположении, что начальная вершина v0   имеет номер 0 и остальные вершины пронумерованы от 1 до N. Сложность рассмотренного алгоритма поиска в ширину, известного под названием «Алгоритм волнового фронта», составляет 0(max(|V|,|E|)).

Пример:

На рисунке   дан  пример работы алгоритма волнового  фронта (при поиске из вершины v0 ) для ориентированного графа.

 

Рисунок 1.7 - Пример работы алгоритма волнового фронта (при поиске из вершины v0 ) для ориентированного графа

 

 

 

Списки смежности ориентированного графа имеют вид

 

 v0→( v2, v3, v1),    v1→( v3),     v2→( v4, v3),

 v3→( v4),    v4→( v1),   v5→( v1),

 v6→( v3, v5),    v7→( v5, v6).

 

Около каждой вершины  vi, поставлена  метка М[vi], которую получает вершина при поиске в ширину. Выделены дуги, составляющие кратчайшие пути из вершины v0  в остальные. 
Отметим, что вершины  v5,  v6   и v7  не  достижимы из v0  и их начальные метки +∞ остались без изменения. При рассмотренном ходе алгоритма массив PR  будет содержать следующие номера вершин : PR[v0] = 0,  PR[v1] = 0,  PR[v2] = 0,  PR [v3] = 0,  PR[v4] = 2. Для остальных вершин соответствующие значения не определены, поскольку они не «посещались».

  Используя массив  PR, восстановим кратчайший путь из вершины v0  в вершину   v4.  Поскольку PR[v4] = 2, а PR[v2] = 0, искомый путь есть  v0, v2, v4.

 

1.8 Топологическая сортировка

 

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

 

Рисунок 1.8 – Пример ориентированного неотсортированного графа

 

  Из рисунка 1.8 видно, что граф не отсортирован, так как ребро из вершины с номером 4 ведет в вершину с меньшим номером (2).Существует несколько способов топологической сортировки - из наиболее известных: алгоритм Демукрона. Будем использовать метод топологической сортировки с помощью обхода в глубину.

Суть алгоритма

Запускаем обход в глубину, и когда вершина обработана, заносим  ее в стек. По окончании обхода в  глубину вершины достаются из стека. Новые номера присваиваются  в порядке вытаскивания из стека. Во время обхода в глубину используется 3 цвета. Изначально все вершины белые. Когда вершина обнаружена, красим ее в серый цвет. Когда просмотрен список всех смежных с ней вершин, красим ее в черный цвет. Рассмотрим данный алгоритм на примере:

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

  Переходим к вершине номер 1. Красим ее в серый цвет.

  Существует ребро из вершины номер 1 в вершину номер 4. Переходим к вершине номер 4 и красим ее в серый цвет.

  Существует ребро из вершины номер 4 в вершину номер 2. Переходим к вершине номер 2 и красим ее в серый цвет.

  Из вершины номер 2 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 2 в черный цвет и кладем ее в стек.

 Существует ребро из вершины номер 4 в вершину номер 3. Переходим к вершине номер 3 и красим ее в серый цвет.

 Из вершины номер 3 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 3 в черный цвет и кладем ее в стек.

  Из вершины номер  4 нет рёбер, идущих не в черные  вершины. Возвращаемся к вершине  номер 1. Красим вершину номер  4 в черный цвет и кладем  ее в стек.

 Из вершины номер 1 нет рёбер, идущих не в черные вершины. Красим её в черный цвет и кладем в стек. Обход точек закончен. Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов.

 

 

 

 

 

 

2 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ

 

 

2.1 Реализация алгоритмов на языке программирования Pascal ABC

 

Рисунок 2.1- Поиск в глубину

 

Рисунок 2.2- Поиск в ширину

 

Рисунок 2.3- Справка о пользователе и рекомендации к программе

 

 

Реализация алгоритмов на языке программирования С++

 

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

 

Рисунок 2.5 Поиск в ширину.

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

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

В этой связи в курсовой работе рассмотрены наиболее перспективные  алгоритмы поиска в графах и их программная реализация.

 

 

СПИСОК ЛИТЕРАТУРЫ

 

1. Порублев И.Н., Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач. –М.: ООО «И.Д.Вильямс», 2007. – 480.
2. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. – 2-е изд. – СПб.: Питер, 2008. – 364 с.
3. Седжвик Роберт Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», 2009.– 688 с.
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: Вильямс, 2006. – 960 с.
5. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. – Москва: Техносфера, 2006. – 368с.
6. Алгоритмы на графах. http://it.kgsu.ru/TI_12/algp_001.html.
7. Алгоритм поиска в глубину и в ширину http://www.sgu.ru/prcnit/teach/2.php.

 

 

 

ПРИЛОЖЕНИЕ А

 

Блок-схема основной  программы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Блок-схема процедуры  breadth_search

   

 

Блок-схема процедуры  depth_search

 

 

 

 

 

Procedure Depth

 

Блок-схема процедуры  spravka

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ Б

 

Листинг программы на языке  Pascal

 

program search;

uses crt;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Var A, B,w : integer;

st: string;

 

 

Procedure breadth_search(A, B: integer);

 Var

  Visited: array[1..n] of boolean;

  Prev: array[1..n] of integer;

  c: array[1..n] of integer;

  head, tail: integer;

  f: boolean;

  i, v, k: integer;

Begin

   head:=1;

   tail:=1;

   f:=False;

 For i:=1 to n do

 Begin

 Visited[i]:=False;

 Prev[i]:=0

 End;

  C[tail]:=A;

  Visited[A]:=True;

  While (head<=tail) and not f do

  Begin

  v:=C[head];

  head:=head+1;

 For k:=1 to n do

  if m[v, k] and not Visited[k] then

  Begin

  tail:=tail+1;

  C[tail]:=k;

  Visited[k]:=True;

  Prev[k]:=v;

  if k=B then

   Begin

    f:=true;

   break

End

End

End;

if f then

Begin

k:=B;

Write(B);

While Prev[k]<>0 do

Begin

Write('<--', Prev[k]);

k:=Prev[k]

end

End

else

Write('Пути из ', A, ' в ', B, ' нет')

end;

 

Procedure depth_search(A, B: integer);

<