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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 3.6.

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

Таблиця 3.1.

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

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

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

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

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

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

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

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

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

6. Уилсон Р.

Введение

в теорию графов.- М., 1977.

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

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