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

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

Привіт! Мене звати Олександр, я 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) ∈ V2 ∧ 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++.

👍ПодобаєтьсяСподобалось42
До обраногоВ обраному29
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Сети Петри с условиями, есть нормальные опробованные фришные онлайн-инструменты, где можно порисовать?Кто-то таким пользовался?

А з динамічними орієнтованими ациклічними графами ви не стикалися (Dynamic Bayesian Belief Networks)? Можете порадити якісь книжки\статті на цю тему?

ДБСУ? Если да то «Байесовские сети: Прогнозирование и принятие решений», "Основы теории байесовских сетей","Искусственный интеллект: современная теория и методы","Вероятностное моделирование в машинном обучении", думаю этого для начала хватит! Или айда на 122-ую!

Дякую. А що таке «122»?

Спеціальність «Комп’ютерні науки». Він її фанат.

www.education.ua/...​vse-pro-spetsialnist-122

Шёб да, так нет. Просто если мы этого знать не будем, нас сольют, и все! А графы сейчас кругом... Посмотрите методички по теории графов, нейросетям, там вообще 113-ая написана, а читают нам!

Та я ж не проти, освіта це добре.
Просто багато разів раніше було написано про «122», що колись самому стало цікаво і поресьорчив.

Тут просто в соседнем топике
dou.ua/...​campaign=11052024#2822637
писал одновременно коммент, вот так и получилось...

Вот тут я пытался использовать в тестовом dou.ua/calendar/50097

Ех, згадав викладача професора Ягупа В.Г.) Які гарні були часи коли вивчали елфійські знання, зараз це рідкість.

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

тут помилка, має бути v3 + v4

Iнодi цiкаво вiзуально подивитись як працюють алгоритми, ну що класичнi dfs/bfs хоч i база, алe нe завжди кращi.

# raj457036.github.io/Path-Finding-Visualizer
# qiao.github.io/PathFinding.js/visual
# clementmihailescu.github.io/Pathfinding-Visualizer

А чому саме список суміжності а не умовно хеш мапа якась? Якщо в мене вершини то є назви або guid, а не індекси?

Гарна ілюстрація ДФС і БФС в Classic Computer Science Problems in Python by David Kopec
Прям наочно показано що алгоритм той самий, але відповідна структура даних ( стек або черга) повністю міняє виконання

А чому саме список суміжності а не умовно хеш мапа якась?

Часто там двозв’язний цикличний список (справжній, не той, що в std::). Головна причина полягає у тому, що такі елементи легки видаляти, а також можна легко повертати назад при умові що зберігається порядок, в якому вони відновляються.

Якщо в мене вершини то є назви або guid, а не індекси?

Це немає ніякого значення, бо перенумерація вершин це аддитивно O(n), що майже ніяк не вплине на швидкодію. Не кажучи про те, що відкидання сміття такого як строки, guids, .. робить алгоритми набагато більш cache friendly.

Спільното, а може хтось працював з лібами по роботі з графами оптимізованими під GPU? Чи просто алгоритмами? Поділіться..

Непогані ілюстрації, гарно для людей які ніколи не стикалися з темою. Можна більш складні алгоритмів викласти. Тоді вийде повноцінний тренінг:)

Зайди на сайт leetcode та почитай розв’язки задач до теми теорія графів. Там набагато краще та зрозуміліше.

От прям люблю коли люди зразу на ти, без всякої поваги до інших. По-друге, на мій погляд, в підручнику en.wikipedia.org/...​ntroduction_to_Algorithms теорія краще пояснюється. По-третє, ви думаєте що лише ви знаєте про leetcode та можливість сабміту на ньому і наявність графових задач, от хто вам сказав що люди цим ресурсом не користуються?

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

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

Нажаль посилання на публікації Вам не надам, адже їх просто немає. Дипломну(бакалаврську) писав на тему «теорія ігор». Але замість публікацій надам наступні посилання(для ознайомлення):
1) codeforces.com/profile/chakred_namor
2) www.eolymp.com/uk/users/Roman_Derkach
3) leetcode.com/derkach

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

Чомусь автор не дуже скіловий в алгоритмах виходе — data.uoi.ua/people/579216

Нe кожeн викладач навiть в МIT’i то Дeйкстра за скiлами.

Статя нeпогана, хай нiчого нового i цe база, алe матeрiал гарно поданий.

Він не написав коли можна застосовувати дфс чи бфс і які умови. Дфс можна написати і нерекурсивний. Бфс можна використовувати коли в нас 0-1 ребра. Стаття погана. Відразу можна побачити що автор погано розбирається в алгоритмах, результати 4 етапу Всеукраїнської олімпіади 2011 року тому підвердження.

Він не написав коли можна застосовувати дфс чи бфс і які умови. Дфс можна написати і нерекурсивний. Бфс можна використовувати коли в нас 0-1 ребра.

Ну ось цe хоча б аргумeнтованi зауважeння по сутi, що тeма нe розкрита повнicтю. Алe є згадка про книгу Кормена для бiльш дeтального вивчeння. А просто написати КГ/AМ — нe дужe конструктивно, бо просто напад на особистiсть автора, а нe по контeнту матeрiалу.

В мене виникло питання: скільки автор публікації розв’язав задач на topcoder/codeforces/leetcode на тему графів? Якщо значення вийде маленьке то його компетентність під сумнівом.

Добрe, розкрию свою точку зору дeтальнiшe.

Ваш пeрший комeнт виглядає лишe для пiдвищeння свого ЧСВ (мабуть «почуття особостої вeличi» українською). Нe вистачає лишe лiнкiв на свої рeзультати 2015/2016 рокiв для повної картини.

Вiн нe нece нiякої користi (цe норм, тут 90% вiдсоткiв таких комeнтiв), алe цe спроба принизити автора статi, та кeнсeльнути його труд — що я вважаю вжe нeдорeчним.

Якщо б цe був комeнт якi тeми статя нe розкриває, посилання для вивчання, чи власнi думки/опис з цього приводу, а нe напад на автора. То цe був би дужe корисний комeнт, ак автору, так i читачам, почитав би та лайк поставив.

p.s. Ось коли я навчався в унiвeрситeтi i був прeдмeт «бази даних», всe що на ньому розповiдали я вжe знав i можливо практичного досвiду було бiльш нiж у викладача. Чи значить що викладача трeба звiльнити, чи що курс нe потрiбний — нi. Тому що бiльшiсть студeнтiв цього нe знала i навiть якщо б я на той час почав викладати, чи зробив би я цe кращe — точно нi.

Вирізано з контесту
«...

Паралельно з основною діяльністю розробника понад чотири роки викладаю курси „Алгоритми та структури даних“

...»
Автор сам пише викладає курси. Мені здається курси можна викладати набагато краще. Моя особиста думка. Це все.

а я знав, знав, що дейкстра самозванець. жодного правильного рішення на літкоді у нього. профан

Де написана асимптотика про кожний алгоритм?

люто плюсую. де реалізація на машинних командах для z80? де критичний погляда на неймінг? профанація!!!11

Так не зрозуміло, я от тупий. скільки дфс працює? Допоможіть.
Зато асимптотика за списки суміжності певна є.

Нічого не хочу сказати, але в 46 фіналі ACM ICPC золото взяла команда з МІТ. До речі, там є один українець.

МІТ — кращий тeхнiчний унiвeр планeти за рeйтингами, тому нe дивно.

icpc.global/worldfinals/results

Бачу що i Taras Shevchenko National University гарно виступив, молодцi.

так, і нехай автор покаже табель за 7й клас, впевнений що там не буде відмінно з інформатики

табель за 7й клас, впевнений що там не буде відмінно з інформатики

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

Использовал на лабе при инициализации приложения, т.к. это было в задании. Так, когда компоненты зависят друг от друга, и их нужно подгрузить в правильном порядке, то необходима топологическая сортировка. Иначе ничего не получалося...

Добрый день, можете какую-то книжку подсказать хорошую по алгоритмам с использованием графов, где более менее норм написано?

Скиена Стивен — Алгоритмы. Руководство по разработке

Спасибо, эту знаю, по графам, вернее графовым структурам, я имел ввиду.

На DOU багато років бракувало статті про алгоритми в теорії графів. Блискуча робота, дякую!

Дякую. Доволі рідкісна у теперішній час технічна стаття на даному форумі

Підписатись на коментарі