Графи. 
Обхід графів в ширину і глибину

Міністерство Освіти та Науки України Дніпродзержинський державний технічний університет Факультет електроніки та комп’ютерної техніки Спеціальність програмне забезпечення систем Напрям освіти 6.50 103 «П.І.»

Курс 3

Група ПЗ-09−1д Звіт з виробничої практики Дніпродзержинськ 2012

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

Під час проходження переддипломної практики я буду вивчати та працювати з графами. Теорія графів — розділ дискретної математики, що вивчає властивості графів. У загальному значенні граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якого рахункового множини, а E — підмножина V? V.

Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або знову проектовані будинку, споруди, квартали і т. п. розглядаються як вершини, а з'єднують їх дороги, інженерні мережі, лінії електропередачі і т. п. — як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.

Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.

Саме тому я обрав собі цю тему для аналізу та вивчення під час проходження практики.

граф алгоритм вершина матриця список Постановка завдання

1. Під час проходження переддипломної практики мені було доручено проаналізувати алгоритми обходу графів:

Ш Обход в ширину Ш Обход в глибину

2. Та виконати програмну реалізацію на С++ алгоритмів пошуку в глибину та в ширину.

Графи. Обхід графів в ширину і глибину Представлення графів Граф — це безліч однотипних об'єктів (вершин), деякі з яких пов’язані один з одним якими зв’язками (ребрами). Одна зв’язок завжди з'єднує тільки дві вершини (іноді - вершину саму з собою). Основні різновиди графів:

ь неорієнтовані (звичайні), в яких важливий лише сам факт зв’язку двох вершин ь орієнтовані (орграфа), для яких важливим є ще й напрямок зв’язку вершин ь зважені, в яких важливою інформацією є ще й ступінь (величина, вага) зв’язку вершин Приклади графів різних типів обычный ориентированный взвешенный Для опису графа як структури даних використовуються два способи: матриці суміжності і списки суміжності. Перший спосіб передбачає використання двовимірного масиву чисел, який для простих графів заповнюється тільки значеннями 0 (немає зв’язку) та 1 (є зв’язок), а для виваженого — значеннями ваг. Для звичайного графа матриця суміжності завжди є симетричною відносно головної діагоналі, а для орграфа найчастіше ця матриця не симетрична, що відображає односторонню спрямованість зв’язків.

Для розглянутих вище прикладів матриці суміжності будуть наступними:

Недоліки цього способу:

заздалегідь треба знати хоча б орієнтовний число вершин у графі

для графів з великим числом вершин матриця стає занадто великий (наприклад 1000 * 1000 = 1 000 000 чисел) при малому числі сполучних ребер матриця заповнена в основному нулями Цих недоліків багато в чому позбавлений другий спосіб, заснований на використанні списків суміжних вершин. Тут списки містять рівно стільки елементів, скільки ребер в графі, і крім того вершини і ребра можуть додаватися динамічно. Список суміжних вершин являє собою головний список всіх вершин і безліч допоміжних списків, що містять перелік вершин, пов’язаних з даною. Для розглянутих вище звичайного графа і орієнтованого графа списки суміжності будуть наступними Опис подібної складної списковому структури виконується звичайним чином.

Операції додавання і видалення в порівнянні з деревами мають наступні варіанти:

· додавання нового зв’язку (ребра) між заданою парою існуючих вершин

· додавання нової вершини разом з усіма необхідними зв’язками

· видалення зв’язку (ребра) між двома вершинами

· видалення вершини разом з усіма її зв’язками Додавання нового ребра включає в себе (на прикладі звичайного графа):

· отримання імен пов’язують вершин

· пошук в основному списку першої пов’язують вершини

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

· пошук в основному списку друге зв’язується вершини

· пошук у списку суміжних їй вершин Перший пов’язує вершини і або виведення повідомлення про помилку, або додавання в цей список нового елемента з іменем першої вершини Додавання нової вершини включає в себе:

· запит імені нової вершини разом з іменами всіх пов’язують з нею вершин

· пошук в основному списку імені нової вершини і в разі відсутності її-додавання до основного списку

· формування списку вершин, суміжних знову доданої

· пошук в основному списку всіх суміжних вершин і додавання в їх допоміжні списки нового елемента з іменем нової вершини Видалення ребра проводиться таким чином:

· запит імен двох вершин, між якими розривається зв’язок

· пошук в основному списку кожної з цих вершин

· пошук в кожному з двох допоміжних списків імені сусідньої вершини і видалення відповідного елемента Видалення вершини проводиться таким чином:

· запит імені видаляється вершини

· пошук її в основному списку

· перегляд допоміжного списку видаляється вершини, для кожного елемента якого:

o пошук суміжної вершини в основному списку і видалення з її допоміжного списку елемента, відповідного видаляється вершині

o видалення самого елемента з допоміжного списку

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

Обхід в глибину Пошук в глибину використовує дві структури — стек для запам’ятовування ще не оброблених вершин і список для запам’ятовування вже оброблених.

Пошук виконується наступним чином:

· задати стартову вершину (аналог кореневої вершини при обході дерева)

· обробити стартову вершину і включити її в допоміжний список оброблених вершин

· включити в стек всі вершини, суміжні зі стартовою

· організувати цикл за умовою спустошення стека і всередині циклу виконати:

· витягти з стека чергову вершину

· перевірити по допоміжному списку оброблений цієї вершини

· якщо вершина вже оброблена, то витягти з стека наступну вершину

· якщо вершина ще не оброблена, то обробити її і помістити в список оброблених вершин

· переглянути весь список суміжних з нею вершин і помістити в стек все ще не оброблені вершини Наприклад, для розглянутого вище звичайного графа отримаємо:

· нехай стартова вершина — B

· включаємо B в список оброблених вершин: список = (В)

· поміщаємо в стек суміжні з В вершини, тобто A і E: стек = (А, Е)

· витягаємо з стека вершину E: стек = (А)

· оскільки E немає в списку оброблених вершин, то обробляємо її і поміщаємо в список: список = (В, Е)

· суміжні з E вершини — це A і B, але B вже оброблена, тому поміщаємо в стек тільки вершину А: стек = (А, А)

· витягаємо з стека вершину А: стек = (А)

· оскільки, А немає в списку оброблених вершин, то поміщаємо її туди: список = (В, Е, А)

· суміжні з, А вершини — це B, C, D, E, з яких B і E вже оброблені, тому поміщаємо в стек C і D: стек = (A, C, D)

· витягаємо з стека вершину D: стек = (A, C)

· оскільки D не оброблена, то поміщаємо її в список: список = (B, E, A, D)

· суміжні з D вершини — це, А і С, з яких, А вже оброблена, тому поміщаємо в стек вершину С: стек = (А, С, С)

· витягаємо з стека вершину С: стек = (А, С)

· оскільки С не оброблена, поміщаємо її в список: список = (B, E, A, D, C)

· суміжні з З вершини — це A і D, але вони обидві вже оброблені, тому в стек нічого не заносимо

· витягаємо з стека С, але вона вже оброблена

· витягаємо з стека А, але вона теж вже оброблена

· оскільки стек став порожнім, то завершуємо обхід з результатом (B, E, A, D, C)

Пошук в ширину Працює трохи по іншому: спочатку обробляються всі вершини, суміжні з поточної, а лише потім — їх нащадки. Замість стека для запам’ятовування ще не оброблених вершин використовується черга. Послідовність дій:

· задати стартову вершину (аналог кореневої вершини при обході дерева)

· обробити стартову вершину і включити її в допоміжний список оброблених вершин

· включити в чергу всі вершини, суміжні зі стартовою

· організувати цикл за умовою спустошення черги і всередині циклу виконати:

· витягти з черги чергову вершину

· перевірити по допоміжному списку оброблений цієї вершини

· якщо вершина вже оброблена, то витягти з черги наступну вершину

· якщо вершина ще не оброблена, то обробити її і помістити в список оброблених вершин

· переглянути весь список суміжних з нею вершин і помістити в чергу все ще не оброблені вершини Той же що й раніше приклад дасть такий результат:

· нехай стартова вершина — B

· включаємо B в список оброблених вершин: список = (В)

· поміщаємо в чергу суміжні з В вершини, тобто A і E: черга = (А, Е)

· витягаємо з черги вершину А: черга = (Е)

· тому що вона не оброблена, додаємо її в список: список = (В, А)

· суміжні з, А вершини — це B, C, D і E, поміщаємо в чергу вершини C, D і E: черга = (E, C, D, E)

· витягаємо з черги вершину Е: черга = (C, D, E)

· тому що Е не оброблена, поміщаємо її в список: список = (B, A, E), тобто в першу чергу оброблені обидві суміжні з В вершини

· суміжні з Е вершини — це, А і В, але обидві вони вже оброблені, тому черга новими вершинами не поповнюється

· витягаємо з черги вершину С: черга = (D, E)

· тому що С не оброблена, то поміщаємо її в список: список = (B, A, E, С)

· суміжні з З вершини — це, А і D, поміщаємо в чергу тільки D: черга = (D, E, D)

· витягаємо з черги вершину D: черга = (E, D)

· тому що D не оброблена, поміщаємо її в список: список = (B, A, E, С, D)

· суміжні з D вершини — це, А і С, але обидві вони оброблені, тому черга не поповнюється

· витягаємо з черги вершину Е, але вона вже оброблена: черга = (D)

· витягаємо з черги вершину D, але вона вже оброблена і тому чергу стає порожній, то пошук закінчується з результатом (B, A, E, С, D), що відрізняється від пошуку в глибину.

На закінчення я хочу відзначити кілька завдань, які найбільш часто зустрічаються на графах:

1. знайти шлях найменшої (найбільшої) довжини між двома заданими вершинами

2. виділити з графа дерево, що має найменший сумарний вага ребер (найкоротший покриває дерево)

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

4. знайти в графі такий шлях, який проходить по всіх вершин рівно по 1 разу і має при цьому найменшу сумарну довжину (задача бродячого торговця або комівояжера).

Програмна Реалізація Пошук в глибину Це один з основних алгоритмів на графах.

В результаті пошуку в глибину знаходиться лексикографічно перший шлях в графі.

Алгоритм працює за O (N + M).

Застосування алгоритму

· Пошук будь-якого шляху в графі.

· Пошук лексикографічно першого шляху в графі.

· Перевірка, чи є одна вершина дерева предком інший:

На початку і наприкінці ітерації пошуку в глибину буде запам’ятовувати «час» заходу і виходу в кожній вершині. Тепер за O (1) можна знайти відповідь: вершина i є предком вершини j тоді і тільки тоді, коли starti endj.

· Завдання LCA (найменший загальний предок).

· Топологічна сортування:

Запускаємо серію пошуків в глибину, щоб обійти усі вершини графа. Відсортуємо вершини за часом виходу за спаданням — це і буде відповіддю.

· Перевірка графа на ациклічні і знаходження циклу

· Пошук компонент сильної зв’язності:

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

· Пошук мостів:

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

Реалізація

vector < vector > g; // граф

int n; // число вершин

vector color; // цвет вершины (0, 1, или 2)

vector time_in, time_out; // «времена» захода и выхода из вершины

int dfs_timer = 0; // «таймер» для определения времён

void dfs (int v) {

time_in[v] = dfs_timer++;

color[v] = 1;

for (vector:iterator i=g[v]. begin (); i≠g[v]. end (); ++i)

if (color[*i] == 0)

dfs (*i);

color[v] = 2;

time_out[v] = dfs_timer++;

}

Це найбільш загальний код. У багатьох випадках часи заходу і виходу з вершини не важливі, так само як і не важливі кольори вершин (але тоді треба буде ввести аналогічний за змістом булевський масив used). Ось найбільш проста реалізація:

vector < vector > g; // граф

int n; // число вершин

vector used;

void dfs (int v) {

used[v] = true;

for (vector:iterator i=g[v]. begin (); i≠g[v]. end (); ++i)

if (!used[*i])

dfs (*i);

}

Пошук в ширину Пошук в ширину (обхід в ширину, breadth-first search) — це один з основних алгоритмів на графах.

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

Алгоритм працює за, де — число вершин, — число ребер.

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

Сам алгоритм можна розуміти як процес «підпалювання» графа: на нульовому кроці підпалюємо тільки вершину. На кожному наступному кроці вогонь з кожною вже палаючої вершини перекидається на всіх її сусідів; тобто за одну ітерацію алгоритму відбувається розширення «кільця вогню» в ширину на одиницю (звідси і назва алгоритму).

Більш строго це можна представити таким чином. Створимо чергу, в яку будуть поміщатися гарячі вершини, а також заведемо булевський масив, в якому для кожної вершини будемо відзначати, горить вона вже чи ні (або іншими словами, чи була вона переглянуло).

Спочатку в чергу поміщається тільки вершина, і, а для всіх інших вершин. Потім алгоритм являє собою цикл: поки черга не порожня, дістати з її голови одну вершину, переглянути всі ребра, що виходять з цієї вершини, і якщо якісь з переглянутих вершин ще не горять, то підпалити їх і помістити в кінець черги.

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

Реалізація Реалізуємо вищеописаний алгоритм на мові C + +.

Вхідні дані:

vector < vector > g; // граф

int n; // число вершин

int s; // стартовая вершина (вершины везде нумеруются с нуля)

// чтение графа

…

Сам обхід:

queue q;

q.push (s);

vector used (n);

vector d (n), p (n);

used[s] = true;

p[s] = -1;

while (!q.empty ()) {

int v = q. front ();

q.pop ();

for (size_t i=0; i

int to = g[v][i];

if (!used[to]) {

used[to] = true;

q.push (to);

d[to] = d[v] + 1;

p[to] = v;

}

}

}

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

if (!used[to])

cout << «No path!» ;

else {

vector path;

for (int v=to; v≠-1; v=p[v])

path.push_back (v);

reverse (path.begin (), path. end ());

cout << «Path: «;

for (size_t i=0; i

cout << path[i] + 1 << ««;

}

Програми алгоритму

· Пошук найкоротшого шляху в незваженим графі.

· Пошук компонент зв’язності в графі за .

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

· Знаходження рішення якої-небудь задачі (ігри) з найменшим числом ходів, якщо кожне стан системи можна уявити вершиною графа, а переходи з одного стану в інший — ребрами графа.

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

· Знаходження найкоротшого шляху в 0−1-графі (тобто графі зваженому, але з вагами рівними тільки 0 або 1): досить небагато модифіковані пошук в ширину: якщо поточне ребро нульового ваги, і відбувається поліпшення відстані до якоїсь вершини, то цю вершину додаємо не в кінець, а в початок черги.

· Знаходження найкоротшого циклу в орієнтованому незваженим графі: виробляємо пошук в ширину з кожної вершини, тільки в процесі обходу ми намагаємося піти з поточної вершини по якомусь ребру у вже відвідану вершину, то це означає, що ми знайшли найкоротший цикл, і зупиняємо обхід в ширину; серед всіх таких знайдених циклів (по одному від кожного запуску обходу) вибираємо найкоротший.

· Знайти всі ребра, що лежать на якомусь найкоротшому шляху між заданою парою вершин. Для цього треба запустити 2 пошуку в ширину: з, і з. Позначимо через масив найкоротших відстаней, отриманий в результаті першого обходу, а через — в результаті другого обходу. Тепер для будь-якого ребра легко перевірити, чи лежить він на якомусь найкоротшому шляху: критерієм буде умова .

· Знайти всі веошини, що лежать на якомусь найкоротшому шляху між заданою парою вершин. Для цього треба запустити 2 пошуку в ширину: з, і з. Позначимо через масив найкоротших відстаней, отриманий в результаті першого обходу, а через — в результаті другого обходу. Тепер для будь-якого вершини легко перевірити, чи лежить він на якомусь найкоротшому шляху: критерієм буде умова .

· Знайти найкоротший парний шлях у графі (тобто шлях парної довжини). Для цього треба побудувати допоміжний граф, вершинами якого будуть стану, де — номер поточної вершини,

— поточна парність. Будь-яке ребро вихідного графа в цьому новому графі перетвориться в два ребра і. Після цього на цьому графі треба обходом в ширину знайти найкоротший шлях із стартовою вершини в кінцеву, з парністю, що дорівнює 0.

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

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

1) http://e-maxx.ru/algo/dfs

2) http://e-maxx.ru/algo/bfs

3) http://xn—h1aaalccfe5c.xn—p1ai/strukturyi-i-algoritmyi-obrabotki-dannyix/grafyi.-obxod-grafov-v-shirinu-i-glubinu.html

4) Кормен, Лейзерсон, Ривест, Штайн «Алгоритмы: постоение и анализ»

5) Седжвик «Фундаментальные алгоритмы на *. Том 4»