Всім привіт.
У цій нотатці я вирішив перерахувати основні структури даних, які застосовуються для зберігання графів в інформатиці, а також розповім про ще пару таких структур, які в мене якось само собою викристалізувалися.
Тож почнемо. Але не з самого початку – думаю, що таке граф і які вони бувають (орієнтовані, неорієнтовані, зважені, незважені, з множинними ребрами та петлями чи без них), ми вже всі знаємо.
Тож поїхали. Які ж варіанти структур даних для графозбереження ми маємо.
1. Матричні структури даних
1.1 Матриця суміжності. Матриця суміжності є матрицею, де заголовки рядків і стовпців відповідають номерам вершин графа, а саме значення кожного її елемента a(i,j) визначається наявністю або відсутністю ребер між вершинами i і j (ясно-зрозуміло, що для неорієнтованого графа така матриця буде симетрична, або ж можна домовитися, що всі значення ми зберігаємо лише вище головної діагоналі). Для незважених графів a(i,j) можна задати кількістю ребер із i в j (якщо немає такого ребра, то a(i,j)= 0), а для зважених також – вагою (сумарною вагою) згаданих ребер.
1.2 Матриця інцидентності. У цьому випадку наш граф також зберігається в таблиці, в якій, як правило, номери рядків відповідають номерам його вершин, а номерам стовпців – попередньо занумеровані ребра. Якщо вершина і ребро інцидентні один одному, то у відповідному осередку записується ненульове значення (для неорієнтованих графів записується 1 у разі інцидентності вершини та ребра, для орієнтованих – «1», якщо ребро «виходить» з вершини та «-1», якщо воно до неї «входить» (запам'ятовується досить легко, адже знак «мінус» теж хіба що «входить» у число «-1»)). Для зважених графів знову ж таки замість 1 і -1 можна вказувати сумарну вагу ребра.
2. Перерахувальні структури даних
2.1 Список суміжності. Ну тут начебто все просто. Кожній вершині графа можна, у випадку, поставити у відповідність будь-яку перечислительную структуру (список, вектор, масив, …), у якій зберігатимуться номери всіх вершин, суміжної даної. Для орієнтованих графів заноситимемо в такий список лише ті вершини, в які є «спрямоване» ребро з вершини-ознаки. Для виважених графів реалізація буде складнішою.
2.2 Список ребер. Досить популярна структура даних. Список ребер, як підказує нам Капітан Очевидність, і є власне список ребер графа, кожне з яких задається початковою вершиною, кінцевою вершиною (для неорієнтованих графів тут порядок слідування не важливий, хоча для уніфікації можна використовувати різні правила, наприклад, вказувати вершини в порядку зростання) та вагою (тільки для зважених графів).
Про перелічені вище списки-матриці можна докладніше (і з ілюстраціями) подивитися, наприклад, .
2.3 Масив суміжності. Не найчастіше зустрічається структура. За своєю суттю, він є формою «упаковки» списків суміжності в одну перелічальну структуру (масив, вектор). Перші n (за кількістю вершин графа) елементів такого масиву містять стартові індекси цього ж масиву, починаючи з яких у ньому поспіль записані всі вершини, суміжні даної.
Ось тут я знайшов найзрозуміліше (для себе) пояснення:
3. Вектор суміжності та Асоціативний масив суміжності
Воно так вийшло, що автор цих рядків, не будучи професійним програмістом, проте періодично мав справу з графами, найчастіше мав справу зі списками ребер. Справді, зручно, якщо у графі є множинні петлі та ребра. І ось, у розвиток класичних списків ребер, пропоную приділити увагу і їх «розвитку/відгалуження/модифікації/мутації», а саме: вектор суміжності та асоціативний масив суміжності.
3.1 Вектор суміжності
Випадок (а1): незважений граф
Будемо називати вектором суміжності для невзваженого графа впорядкований набір парної кількості цілих чисел (а[2i], a[2i+1],…, де i нумерується з 0), в якому кожна пара чисел а[2i], a[2i+1 ] задає ребро графа між вершинами а[2i] та a[2i+1] відповідно.
Даний формат запису не містить відомостей, чи є граф орієнтованим (можливі обидва варіанти). З використанням формату для орграфа вважається, що ребро спрямовано з а[2i] в a[2i+1]. Тут і далі: для неорієнтованих графів, за потреби, можуть застосовуватися вимоги до порядку запису вершин (наприклад, щоб першою йшла вершина з меншим значенням присвоєного їй номера).
У C++ вектор суміжності доцільно ставити з допомогою std::vector, звідси і було обрано назву даної структури даних.
Випадок (а2): незважений граф, ваги ребер цілочисленні
За аналогією з випадком (а1) назвемо вектором суміжності для зваженого графа з цілими вагами ребер впорядкований набір (динамічний масив) чисел (а[3i], a[3i+1], a[3i+2],…, де i нумерується c 0), де кожен «триплет» чисел а[3i], a[3i+1], a[3i+2] задає ребро графа між вершинами під номерами а[3i] та a[3i+1] відповідно, а значення a [3i+2] є вага цього ребра. Такий граф може бути як орієнтованим, так і немає.
Випадок (б): незважений граф, ваги ребер нецілочисленні
Вигляду того, що в одному масиві (векторі) не можна зберігати різноманітні елементи, то можлива, наприклад, наступна реалізація. Граф зберігається в парі векторів, в якій перший вектор є вектором суміжності графа без вказівки ваг, а другий вектор містить відповідні ваги (можлива реалізація C++: std::pair ). Таким чином, для ребра, що задається парою вершин під індексами 2i, 2i+1 першого вектора, вага буде дорівнює елементу під індексом i другого вектора.
Ну, а навіщо це треба?
Ну, автору цих рядків для вирішення низки завдань це видалося досить корисним. Ну а з формального погляду, тут будуть такі переваги:
- Вектор суміжності, як і будь-яка інша «перерахувальна» структура, досить компактна, займає менше пам'яті, ніж матриця суміжності (для розріджених графів) відносно реалізується.
- Вершини графа, у принципі, може бути промарковані і негативними числами. Аж раптом знадобиться і така «зворотність».
- Графи можуть містити множинні ребра та множинні петлі, причому з різними вагами (позитивні, негативні, навіть нульові). Жодних обмежень тут немає.
- А ще ребрам можна надавати різні властивості – але про це див.
Однак, треба визнати, швидкого доступу до ребра дана «спискота» не має на увазі. І тут на допомогу поспішає Асоціативний масив суміжності, про що – нижче.
3.2 Асоціативний масив суміжності
Отже, якщо для нас доступ до конкретного ребра, його ваги та інших властивостей є критичним, а вимоги до пам'яті не дозволяють використовувати матрицю суміжності, то подумаємо, як можна змінити вектор суміжності, щоб вирішити це завдання. Отже, ключем є ребро графа, яке можна поставити у вигляді впорядкованої пари цілих чисел. На що це схоже? Чи не на ключ в асоціативному масиві? А якщо так, чому б нам це і не реалізувати? Нехай у нас з'явиться такий асоціативний масив, де кожному ключу – упорядкованій парі цілих чисел – буде поставлено у відповідність значення – ціле чи речове число, що задає вагу ребра. У C++ реалізовувати цю структуру доцільно з урахуванням контейнера std::map (std::map , int> або std::map , double>), або std::multimap, якщо передбачаються множинні ребра. Ну і ось, і у нас вийшла структура для зберігання графів, яка займає менше пам'яті, ніж «матричні» структури, може задавати графи з множинними петлями та ребрами і навіть не має жорстких вимог до невід'ємності номерів вершин (не знаю, кому це треба, але все ж).
4. Структур даних хоч «залийся», а чогось не вистачає
І справді ж: при вирішенні низки завдань у нас може виникнути потреба у присвоєнні ребрам графа будь-яких ознак і, відповідно, їх зберіганні. Якщо можна однозначно звести ці ознаки до цілих чисел, можна зберігати такі «графи з додатковими ознаками» використовуючи розширені версії вектора суміжності і асоціативного масиву суміжності.
Отже, нехай у нас є незважений граф, для кожного ребра якого необхідно зберігати, наприклад, 2 додаткові ознаки, що задаються цілими числами. У цьому випадку можна задати його вектор суміжності як упорядкований набір не «пар», а «квартетів» цілих чисел (а[2i], a[2i+1], a[2i+2], a[2i+3]…) , де a[2i+2] та a[2i+3] і будуть визначати ознаки відповідного ребра. Для графа ж з цілими вагами ребер порядок, загалом, аналогічний (відмінністю буде лише та обставина, що ознаки слідуватимуть після ваги ребра і задаватися елементами a[2i+3] і a[2i+4], а саме ребро задаватиметься не 4-ма, а 5-ма впорядкованими числами). А для графа з нецілочисленними вагами ребер ознаки можна буде записати в його незважений компонент.
При використанні асоціативного масиву суміжності для графів з цілими вагами ребер можливо в якості значення задавати не окреме число, а масив (вектор) чисел, що задають, крім ваги ребра, всі інші необхідні ознаки. При цьому незручністю для випадку нецілочисельних ваг буде необхідність завдання ознаки числом з плаваючою комою (так, це незручність, але якщо таких ознак не так і багато, і якщо не ставити їх надто «хитрими» double, то воно може і нічого) . Отже, в C++ розширені асоціативні масиви суміжності можуть задаватися в такий спосіб: std::map , std::vector> або std::map , std::vector, при цьому першим значенням у «векторі-значенні-по-ключу» буде вага ребра, а далі розташовуються чисельні позначення його ознак.
література:
Про графи та алгоритми взагалі:
1. Кормен, Томас Х., Лейзерсон, Чарльз І., Рівест, Рональд Л., Штайн, Кліффорд. Алгоритми: побудова та аналіз, 2-ге видання: Пер. з англ. - М.: Видавничий дім "Вільямс", 2011.
2. Харарі Френк. Теорія графів. М.: Світ, 1973.
Доповідь автора про ці вектор і асоціативний масив суміжності:
3. Чорноухів С.А. Вектор суміжності та асоціативний масив суміжності як способи представлення та зберігання графів / SA Chernouhov. Adjacency vector and adjacency map of data structures to represent a graph // Збірник статей Міжнародної науково-практичної конференції «Проблеми впровадження результатів інноваційних розробок та шляхи їх вирішення» (Саратов, 14.09.2019 р.). – Стерлітамак: АМІ, 2019, с. 65-69
Корисні інтернет-джерела на тему:
4.
5.
Джерело: habr.com