8 Алгоритми на графах
Ез: у>:х,у еVл хФ у) -для неорієнтованого графа.
Будемо використовувати також позначенняV\ =п,Е \ =m (потужність множини).
Теоретично графів класичним способом представлення графа є матриця інциденцій. Це матриця А з п рядками, що відповідають вершинам, і m стовпцями, що відповідають ребрам. Для орієнтованого графа стовпець, відповідний дузі (х,у)еЕ, містить +1 у рядку, що відповідає вершині х, -1 у рядку, що відповідає вершині у і нулі у всіх інших рядках. Петлю, тобто. дугу виду (х, х), зручно представляти іншим значенням, наприклад, 2, в рядку х.
Для неорієнтованого графа стовпець, що відповідає ребру, містить 1 у рядках, відповідних х і у, і 0 - у всіх інших рядках (рис. 28, рис. 29).
п
0 0 0-1-10 про 0 0 0 0 11-1 0 0 0 0 0-11 (1,2) (1,3) (3,2) (3,4) (5,4) (5, 6) (6,5) Мал. 28 Матриця інцидентів для орієнтованого графа
Мал. 29 Матриця інцидентів для неорієнтованого графа
З алгоритмічної точки зору матриця інциденцій є одним із найгірших способів подання графа, оскільки:
потрібно n х m осередків пам'яті, причому більшість осередків зайнято нулями;
незручний доступом до інформації, т.к. відповідь питання: чи існує дуга (х,у)?яких вершин ведуть ребра з х? - вимагає у разі перебору всіх стовпців, тобто. м кроків.
Трохи кращий спосіб представлення графа за допомогою матриці суміжностіB
розміру n x m, де
bij= 1, якщо існує ребро, що веде з x у y, іbij= 0 - в іншому випадку. При цьому мається на увазі, що
ребро x,y> неорієнтованого графа йде як від x до y, так івід y до x. Тому матриця суміжності для неорієнтованого графа завжди симетрична. Для наших графів матриці суміжності мають вигляд:
Основна перевага матриці суміжності полягає в тому, що за один крок можна відповісти на питання – чи існує ребро з x у y?
Недоліком є той факт, що незалежно від числа ребер обсяг пам'яті, що займається, становитьn2 . На практиці цю незручність іноді можна виправити, зберігаючи цілий рядок або стовпець в одному машинному слові (для малихn).
Більше економним щодо пам'яті (особливо для нещільних графів, колиmнабагато меншеn2 ) є спосіб представлення графа за допомогою списку пар, відповідних його ребрам. Пара (x,y) відповідає дузі (x,y), якщо граф орієнтований, і ребру x,y, якщо граф неорієнтований. У нашому випадку списки пар:
Вочевидь, що у разі обсяг пам'яті становить 2т. Незручністю є велика кількість кроків (порядку m у гіршому випадку) для знаходження безлічі вершин, до яких ведуть ребра з цієї вершини.
Ситуацію можна значно покращити, якщо впорядкувати безліч пар лексикографічно. Тоді можна застосувати двійковий пошук.
Найкращим рішенням у часто є структура даних, яку назвемо списками інцидентності. Вона містить для кожної вершиниVеVсписок вершинітаких, щоV—> ідля орієнтованого графа таV—ідля неорієнтованого графа. Кожен елемент такого списку є записомг, що складається з двох полів:
рядок - вершина графа;
м.слід - покажчик на наступний запис у списку.
Для останнього запису у списку – г.слід = nil. Покажчик на початок кожногосписку зберігається у таблиці ПОЧАТОК. Таким чином ПОЧАТОК - покажчик на початок списку, що містить вершини з множини для орієнтованого графа або > для неорієнтованого графа відповідно.
Весь список позначимо (неформально) СПИСОК[у], а цикл, який виконує деяку операцію над кожним елементоміз цього списку, запишемо як
for ueСПИСОК[v] do .
Зазначимо, що для неорієнтованого графа кожне ребро v> представлено двічі:
через вершинуvу списку СПИСОК[і] та
через вершинуіу списку СПИСОК[у].
Для наших прикладів список інцидентності СПИСОК[у], veV виглядають так:
Багато алгоритмах структура графа динамічно модифікується додаванням і видаленням ребер. У разі вважаємо, що у списку СПИСОК[u] елемент, що містить вершину v, забезпечений покажчиком на елемент списку СПИСОК[v], що містить вершину u, кожен елемент списку забезпечений покажчиком як наступний, а й попередній елемент. Тоді видаляючи певний елемент зі списку, ми можемо легко за обмежену кількість кроків видалити й інший елемент, що представляє те саме ребро, не переглядаючи список, що містить цей елемент.
Число осередків пам'яті, необхідні представлення графа з допомогою списків інцидентності, має порядок (n + m).
оператор P для всіх елементів x X у довільній послідовно-
Обговоримо деякі поняття, пов'язані із записом алгоритмів. Алгоритми будемо записувати неформальною мовою, яка використовує основні конструкції Паскаля. Якщо реалізація якого-небудь фрагмента алгоритму очевидна, то такий фрагмент будемо записувати природною мовою. Також застосовуватимемо деякі неформальні конструкції, наприклад:
існують константи,N такі, що f(n) N
g(n) - деяка задана функція існують константи С, N такі, що f(n) >С g(n) для будь-якого n>N Читається: 0(g(n)) - "порядку не більше ніж g(n) )"
Q(g(n)) - "порядку щонайменше ніж g(n)" Те саме функції/п, т).
Калькулятор
Сервіс безкоштовної оцінки вартості роботи
- Заповніть заявку. Фахівці розрахують вартість вашої роботи
- Розрахунок вартості прийде на пошту та по СМС
Номер вашої заявки
Зараз на пошту прийде автоматичний лист-підтвердження з інформацією про заявку.