Основні алгоритми в теорії графів

💡 Усі статті, обговорення, новини для початківців — в одному місці. Приєднуйтесь до Junior спільноти!

Привіт! Мене звати Олександр, я Senior C++ Engineer в компанії GlobalLogic. Мій шлях у ІТ розпочався близько 8,5 років тому. Починав з позиції трейні, за 2,5 роки пройшов шлях до рівня middle-розробника. В GlobalLogic я працюю близько шести років над healthcare-проєктом. У роботі використовую Qt та QML. Паралельно з основною діяльністю розробника понад чотири роки викладаю курси «Алгоритми та структури даних» та «Gof Design Patterns» в навчальній програмі GlobalLogic Education.

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

Розглянемо два основних типи обходу графів: пошук у глибину (DFS) та пошук у ширину (BFS). Визначимо їх особливості, переваги, а також практичне застосування.

Що таке графи

Пропоную почати з визначення графа. Формально, граф — це множина, яка складається з трьох множин: G = (V, E, I), де

V — множина вершин,

E — множина ребер,

I: E → {{x, y} | (x, y) ∈ V² ∧ x ≠ y} — функція, яка ставить у відповідність пари вершин до ребер.

Наприклад, для цього графа множини V, E та I матимуть наступний вигляд:

V = { v0, v1, ..., v15 }

E = { e0, e1, ..., e19 }

I = { e0 → {v0, v1},

e1 → {v1, v2},

...

e19 → {v14, v15} }

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

Основні типи графів

Графи бувають орієнтовані та неорієнтовані. У неорієнтованих графах ребра не мають напрямку, тобто зв’язок між двома вершинами є двостороннім. Орієнтовані графи містять ребра, кожне з яких має напрямок від однієї вершини до іншої.

Орієнтований граф:

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

Зважений граф:

Також є більш «екзотичні» варіанти графів:

Мультиграф — граф, що дозволяє наявність множинних ребер між однією парою вузлів.

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

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

Способи подання графів у пам’яті

Очевидно, що для роботи з графами необхідно ефективно представляти їх у пам’яті комп’ютера. Існує два основних способи представлення графів — матриця суміжності та список суміжності.

Матриця суміжності є двовимірним масивом, де елемент за індексами i та j вказує на наявність — 1 (або відсутність — 0) ребра між вершинами i та j. Якщо граф є неорієнтованим, то така матриця буде симетричною відносно основної діагоналі.

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

Якщо представити за допомогою матриці суміжності орієнтований граф, де зв’язки мають напрямок, матриця втрачає симетричність.

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

Для кращого розуміння наведу приклад. За основу візьмемо простий (незважений неорієнтований) граф:

Матриця суміжності для такого графа буде мати такий вигляд:

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

Тепер подивимося, як той самий граф представляється за допомогою списку суміжності:

Маємо список списків. Розмір основного списку відповідає кількості вершин у графі, які нумеруються від 0 до 14. Таким чином, розмірність основного списку по вертикалі також становить 14. Для кожної вершини формується власний список, який містить вершини, з якими вона має безпосередній зв’язок. Для прикладу розглянемо вершину 8. Вона має безпосередній зв’язок із вершинами 4, 7, 9 і 10.

Пошук у глибину (DFS) та пошук у ширину (BFS)

Велика кількість алгоритмів на графах базується на двох базових обходах вершин. Це пошуки у глибину (DFS — Depth First Search) та ширину (BFS — Breadth First Search). У цілому, робота з графами неможлива без розуміння цих фундаментальних алгоритмів.

Пошук у глибину (DFS)

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

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

Пропоную розглянути, як цей спосіб працює на простому графі. Крім стека будемо зберігати порядок обходу вершин (Sequence).

Спочатку необхідно вибрати стартову вершину. Нехай у даному прикладі це буде v0. Додаємо її у Stack та Sequence. До речі, вершини, які на цю мить знаходяться в стеку, утворюють клас поточних вершин.

Stack: v0

Sequence: v0

На наступному кроці необхідно визначити сусідню невідвідану вершину. Це v5. Додаємо її у Stack та Sequence. Будемо вважати, що вершина стека Stack знаходиться зліва.

Stack: v5 v0

Sequence: v0 v5

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

Stack: v3 v5 v0

Sequence: v0 v5 v3

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

Значення:

Stack: v4 v8 v10 v13 v14 v6 v1 v3 v5 v0

Sequence: v0 v5 v3 v1 v6 v14 v13 v10 v8 v4

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

Значення:

Stack: v8 v10 v13 v14 v6 v1 v3 v5 v0

Sequence: v0 v5 v3 v1 v6 v14 v13 v10 v8 v4

Таким чином, новим верхнім елементом стека є вершина v8. З неї ми підемо у v7, оскільки з усіх невідвіданих вона має найменший індекс.

Аналогічна ситуація складеться у вершині V7. Ми позначимо її як відвідану та викинемо зі стека, оскільки вона тупикова.

Значення:

Stack: v8 v10 v13 v14 v6 v1 v3 v5 v0

Sequence: v0 v5 v3 v1 v6 v14 v13 v10 v8 v4 v7

Алгоритм завершує роботу, коли стек стає порожнім:

Stack:

Seq: v0 v5 v3 v1 v6 v14 v13 v10 v8 v4 v7 v9 v11 v12 v2

Пошук у ширину (BFS)

На відміну від DFS, BFS не будує поточний шлях. Він намагається «йти» у всі сторони одночасно та рівномірно. Обхід базується на структурі даних Queue (черзі). Як і для попереднього обходу, будемо підтримувати порядок відвідування вершин у Sequence. Також додамо масив Parents: для вершини i він буде зберігати «батьківську» вершину, тобто ту, з якої ми прийшли у i.

При ініціалізації Parents[i] = i. Насправді для роботи алгоритму BFS масив Parents безпосередньо не потрібен. Однак він допоможе відновити найкоротший шлях з початкової вершини до всіх інших. Про це згадаємо пізніше.

На етапі ініціалізації додаємо стартову вершину v0 у чергу. Відповідно, вона також буде першим елементом у Sequence.

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

Розглянемо декілька кроків алгоритму на тому ж графі.

Після першого кроку алгоритму отримаємо наступне:

Queue: v5

Sequence: v0 v5

Parents: v0 v1 v2 v3 v4 v0 v6 v7 v8 v9 v10 v11 v12 v13 v14

Зверніть увагу, що елемент масиву Parents за індексом 5 тепер дорівнює 0. Тобто, іншими словами, це говорить про те, що у v5 ми прийшли з v0.

На наступному етапі алгоритму вершину v5 буде видалено з черги, а вершини v3 та v4 буде додано в кінець, оскільки вони були невідвіданими і досяжними з v5. Зверніть увагу на зміни в масиві Parents.

Queue: v3 v4

Seq: v0 v5 v3 v4

Parents: v0 v1 v2 v5 v5 v0 v6 v7 v8 v9 v10 v11 v12 v13 v14

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

Queue:

Sequence: v0 v5 v3 v4 v1 v2 v8 v6 v7 v9 v10 v14 v11 v13 v12

Значення Parents для всіх вершин будуть виглядати так:

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

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

Саме для цього ми обчислювали масив Parents. Визначимо найкоротший шлях від стартової вершини v0 до v9. Його ми будемо відновлювати з кінця. Нас цікавить вершина v9. З якої вершини ми потрапили в неї? З вершини v8 (див. масив Parents).

Далі ми дізнаємося, що у вершину v8 ми прийшли з v4, а перед тим була вершина v5. Батьківською вершиною для v5 є v0. При наступній перевірці бачимо, що у в v0 ми потрапили з v0. Таке зациклення є сигналом для завершення алгоритму відновлення шляху. Таким чином, ми отримали: v9, v8, v4, v5, v0. Залишилося лише розвернути отриману послідовність.

Пошук компонент зв’язності

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

Тут, наприклад, наведено граф, що складається з трьох компонент зв’язності:

Коротко сформулюю ідеї визначення кількості компонент зв’язності у графі.

Візьмемо довільну вершину (зазвичай беруть v0) та запустимо з неї BFS або DFS. Обхід відвідає всі доступні вершини. Якщо всі вершини з’єднані між собою шляхами, тоді не залишаться невідвідані вершини, і це означатиме, що існує лише одна компонента зв’язності.

В іншому випадку виберемо з невідвіданих вершин довільну та знову запустимо BFS або DFS. Так будемо робити доти, поки не залишаться невідвідані вершини. Кількість запусків алгоритму обходу графу і буде кількістю компонент зв’язності.

Що далі?

Розглянуті обходи графу є основою для складніших алгоритмів. Наприклад, алгоритми Дейкстри та Прима базуються за BFS. Алгоритми пошуку мостів та точок з’єднання — на DFS. Можу порадити книгу Т. Кормена «Вступ до алгоритмів» — вона добре розкриває тему графів, а також інші розділи алгоритмів та структур даних.

Приклад реалізації на С++

У цій секції хочу навести ключові ідеї реалізації мовою С++.

Подання графа в пам’яті

Для представлення графа будемо використовувати список суміжності. Як контейнер я зазвичай використовую вектор (std::vector), елементами якого є вектори з елементами типу int.

using AdjacencyList = std::vector<std::vector<int>>;

Однак, доцільною може бути й структура std::vector<std::list<int>>.

Формат вхідних даних

Для зчитування даних з консолі про граф, зазвичай, використовується наступний формат:

• перший рядок містить два числа n та m — кількість вершин та кількість ребер відповідно;
• наступні m рядків містять інформацію про ребра графа. Для незваженого графа це будуть пари чисел, кожна з яких визначає ребро між двома вершинами. Для зваженого графа подаються трійки чисел, де останнє — вага поточного ребра (у тексті розглядаємо лише перший варіант).

Таким чином, для неорієнтованого графа, який ми розглядали у прикладі, вхідні дані матимуть вигляд:

15 18

0 5

4 8

9 10

6 14

11 12

13 10

10 8

2 3

1 6

4 3

11 9

7 8

3 1

10 11

14 13

9 8

3 5

4 5

Приклад коду для зчитування графа може виглядати так (перевірки на коректність вхідних даних опущено):

AdjacencyList graph;

int n; // кількість вершин

std::cin >> n;

graph.resize(n); // знаємо кількість елементів у основному векторі

int m;

std::cin >> m; // кількість ребер

for (int i = 0; i < m; ++i)

{

         int x, y;

         std::cin >> x >> y;

         // Оскільки граф неорієнтований, значення додаємо симетрично

         graph[x].push_back(y);

         graph[y].push_back(x);
 
}

Імплементація DFS

На етапі імплементації обходів графу потрібно мати масив типу bool розмірністю n (кількість вершин), де кожен елемент буде сигналізувати, чи дана вершина вже є відвіданою. Тут також використовую std::vector:

vector<bool> visited(n, false); // на початку всі вершини є невідвіданими

Далі наведено рекурсивну імплементацію обходу DFS:

// param _v - поточна вершина

void dfs(int _v)

{

       visited[_v] = true; // зробили поточну вершину відвіданою

       // Обробляємо поточну вершину. Наприклад, виводимо на екран

       std::cout << _v << endl;

       /* Перебираємо усі сусідні вершини. Якщо знаходимо таку, що є невідвіданою, запускаємо з неї dfs рекурсивно */

       for (int i = 0; i < graph[_v].size(); ++i)

       {

                int current = graph[_v][i];

                if (!visited[current])

                {

                         dfs(current);

                }

       }

}

Імплементація BFS та пошуку найкоротшого шляху

Як я зазначав вище, обхід BFS базується на структурі даних «черга». Для цього використаємо std::queue.

Заведемо вектор parents для відновлення шляху:

std::vector<int> parents;

parents.resize(n); // n - кількість вершин

for (int i = 0; i < parents.size(); ++i)

{

         parents[i] = i;

}

Також не забуваємо, що вектор visited повинен бути ініціалізований нулями як і в попередньому обході.

// param _v - поточна вершина

void bfs(int _v)
{
       visited[_v] = true; // зробили поточну вершину відвіданою

       queue<int> q;
       q.push(_v);

       while (!q.empty())
       {
              int top = q.front();

              // тут можна виконати додаткові дії з поточною вершиною

              q.pop();

              // додаємо усі сусідні невідвідані вершини у чергу
              for (int i = 0; i < graph[top].size(); ++i)
              {
                      int current = graph[top][i];

                      if (!visited[current])
                      {
                                // у вершину current попали з top
                                parents[current] = top
                                q.push(current);
                                visited[current] = true;
                      }
                }
        }
}

Тепер, скажімо, ми хочемо дізнатися найкоротший шлях з вершини start (та, з якої запускали BFS) у вершину end (будь-яка інша). Заведемо вектор way, у якому будемо зберігати цей шлях.

std::vector<int> way;

Наступний код реалізує відновлення шляху. Перевірку його наявності було опущено.

int current = end;

while (current != parents[current])

{

       way.push_back(current);

       current = parents[current];

}

way.push_back(start); // стартову вершину необхідно додати окремо

Таким чином, вектор way містить найкоротший шлях від end до start.

Live coding

Хочу ще раз наголосити, що наведений вище код є мінімалістичним та слугує для поверхневого ознайомлення із можливою реалізацією розглянутих алгоритмів. У моєму live-кодингу я детально пояснюю та реалізую усі описані та деякі додаткові алгоритми на графах мовою C++.