Пошук шляхів у графі (реферат)

Реферат на тему:

Пошук шляхів у графі

Користуючись методами, викладеними в попередньому розділі, можна
визначити зв’язність (тобто наявність або відсутність шляху) між
будь-якими вершинами vi і vj заданого графа G =(V,E ). Однак часто буває
необхідним не просто встановити існування шляху між заданими вершинами,
але й знайти послідовність вершин і ребер (шлях), що веде з vi у vj.

Крім того, для різних практичних застосувань теорії графів важливою є
проблема систематичного обходу (перебору) всіх вершин і/або ребер графа.

Двома класичними методами розв’язання цих проблем є: метод або алгоритм
пошуку (обходу графа) вшир та метод або алгоритм пошуку (обходу графа)
вглиб.

Сформулюємо постановку проблеми пошуку та обидва методи її розв’язання.

Нехай задано граф G =(V,E ), VO (V ( множину початкових вершин і VK (V (
множину кінцевих (заключних, цільових) вершин графа G. Необхідно знайти
шлях з деякої вершини v (VO в одну з вершин w (VK , тобто знайти
послідовність ребер (vi,vi +1)(E, і =1,2,…,t (1 таку, що v1= v і
vt= w.

Зокрема, множина початкових вершин VO і/або множина кінцевих вершин VK
можуть містити тільки по одній вершині. Такі вершини природно називати
початковою і кінцевою вершинами графа G.

Для опису алгоритмів нам знадобляться три списки ребер ВІДКР, ЗАКР і
РОЗВ. Крім того, для вершини v (V через S (v) будемо позначати множину
всіх вершин w (V таких, що в графі G існує ребро (v,w)(E. Такі вершини w
часто називають синами вершини v, а множину S (v) ( множиною синів
вершини v.

Для зручності додамо до множини вершин V графа G “порожню” вершину p, а
до множини ребер – “порожні” ребра виду (р,v), де v (VO. При визначенні
шляху з VO у VK “порожні” ребра не враховуються.

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

Алгоритм пошуку вшир / вглиб.

1. Всі “порожні” ребра розмістити у списку ВІДКР (у довільному порядку).

2. Якщо ВІДКР = (, то РОЗВ = ( (тобто сформульована задача не має
розв’язку) і алгоритм завершує свою роботу.

3. Закрити перше ребро (v,w) з ВІДКР, тобто перенести ребро (v,w) зі
списку ВІДКР у список ЗАКР.

4. Якщо вершина w закритого ребра є кінцевою вершиною (w(VK), то шуканий
список РОЗВ (тобто шуканий шлях з VO у VK) міститься серед ребер списку
ЗАКР і може бути виділений з нього послідовно, починаючи з останнього
закритого ребра шляху. Зауважимо, що при побудові результуючого шляху
для кожного з ребер (v,w) списку ЗАКР необхідно вибирати
ребро-попередника (u,v) так, що воно є першим ребром з кінцем v у списку
ЗАКР. Алгоритм завершує свою роботу.

У противному разі (w (VK) перейти до пункту 5.

5. Визначити S (w) ( множину синів вершини w останнього закритого ребра,
а також множину ребер R (w)={(w,z) | z (S (w) }.

Розмістити у списку ВІДКР усі ребра з множини R (w) \ (ВІДКР ( ЗАКР)
після / перед усіх ребер, що вже містяться в цьому списку.

6. Перейти до пункту 2.

Відмінність між обома алгоритмами пошуку знаходиться в позиції 5 і
полягає в тому, що в алгоритмі пошуку вшир необхідно розміщувати
відповідні ребра після, а в алгоритмі пошуку вглиб ( перед усіма
ребрами, що знаходяться в списку ВІДКР.

Для наведених алгоритмів вживають скорочені назви АПШ і АПГ (відповідні
англійські назви ( BFS (breadth first search) i DFS (depth first
search)).

Таким чином, для АПШ список ВІДКР є чергою, тобто такою сукупністю
елементів, в якій нові елементи розміщуються в кінці сукупності, а
елемент, що “обслуговується” (закривається), вибирається з голови
(початку) цієї сукупності. У той час для АПГ список ВІДКР є так званим
стеком, тобто сукупністю, в якій елементи, що додаються до сукупності, і
елементи, що відбираються для “обслуговування”, розміщуються тільки на
початку сукупності – у верхівці стеку (за принципом: “останній прийшов
– перший обслуговується”).

Приклад 3.8. Розглянемо дію алгоритму пошуку вшир для графа, зображеного
на рис.3.6 (див. таблицю 3.1). Вважаємо, що VO= {3} i VK= {11}.

Рис.3.6

Кожний рядок таблиці описує результат виконання одного циклічного кроку
(позиції 2(6) алгоритму. Оскільки список ЗАКР тільки поповнюється і на
кожному кроці поповнюється тільки одним ребром, то в таблиці записуємо
лише це ребро (не повторюючи всі елементи, які ввійшли до складу ЗАКР на
попередніх кроках). Нагадаємо також, що ребра (v,w) і (w,v) збігаються.

Таблиця 3.1.

Алгоритм пошуку вшир (АПШ)

Крок ВІДКР ЗАКР w R (w)

0 (p,3)

1 (3,2),(3,4) (p,3) 3 (3,2),(3,4)

2 (3,4),(2,1),(2,4),(2,5),(2,6) (3,2) 2 (2,1),(2,4),(2,5),(2,6)

3 (2,1),(2,4),(2,5),(2,6),(4,5),(4,8) (3,4) 4 (4,5),(4,8)

4 (2,4),(2,5),(2,6),(4,5),(4,8) (2,1) 1

5 (2,5),(2,6),(4,5),(4,8) (2,4) 4

6 (2,6),(4,5),(4,8),(5,8) (2,5) 5 (5,8)

7 (4,5),(4,8),(5,8),(6,7) (2,6) 6 (6,7)

8 (4,8),(5,8),(6,7) (4,5) 5

9 (5,8),(6,7),(8,7),(8,9) (4,8) 8 (8,7),(8,9)

10 (6,7),(8,7),(8,9) (5,8) 8

11 (8,7),(8,9) (6,7) 7 (7,12),(7,11),(7,9),(7,10)

12 (8,9),(7,12),(7,11),(7,9),(7,10) (8,7) 7

13 (7,12),(7,11),(7,9),(7,10) (8,9) 9

14 (7,11),(7,9),(7,10),(12,10),(12,11) (7,12) 12 (12,10),(12,11)

15 (7,9),(7,10),(12,10),(12,11) (7,11) 11

Алгоритм завершує свою роботу на п’ятнадцятому кроці. Аналізуючи список
ребер ЗАКР від його кінця до початку, будуємо список РОЗВ, тобто
знаходимо шуканий шлях від вершини 3 у вершину 11:
3,(3,2),2,(2,6),6,(6,7),7,(7,11),11. Довжина цього шляху ( 4.

Радимо побудувати аналогічну таблицю для алгоритму пошуку вглиб шляху з
вершини 3 у вершину 11 і порівняти дію та результати обох алгоритмів.

Список літератури

1. Харари Т. Теория графов.- М.,1973.

2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов
В.И., Тышкевич Р.И.- М., 1990.

3. Зыков А.А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р. Введение в теорию графов.- М., 1977

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980