Розділяй і володарюй.

Розраховує найкоротші шляхи до всіх вершин.

Пошук у ширину з обрізанням.

Жадібний алгоритм, що на кожному кроці вибирає ребро з найменшою вагою.

Пошук у глибину з обрізанням.

Не гарантує знаходження найкоротшого шляху у графах із циклами.

Не може обробляти негативні ваги ребер.

Працює лише з незваженими графами.

Має експоненціальну годинну складність.

19.

24.

25.

22.

Завдання про обхід лабіринту

Завдання про пошук найкоротшого шляху.

Завдання про орієнтацію графа.

Завдання комівояжера.

Завдання для фарбування графа

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

Кожен ейлерів граф є зв'язним.

Ейлерів цикл починається і закінчується в одній і тій самій вершині.

Кожен зв'язний граф є ейлеровим.

Ейлерів цикл проходитиме через кожне ребро графа рівно один раз.

Алгоритм Дейкстри

Алгоритм Крускала

Алгоритм Беллмана-Форда

Алгоритм обходу в глибину

Алгоритм Флойда-Воршелла

Граф, у якому існує цикл, що проходить через кожне ребро один раз.

Граф, у якому всі вершини мають непарний степінь.

Граф, у якому всі вершини мають парний степінь.

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

Граф, у якому всі ребра мають однакову вагу.

Для будь-якого зв'язного графа, в якому всі вершини мають парний ступінь.

Для будь-якого ациклічного графа.

Для будь-якого зв'язного графа.

Для будь-якого повного графа.

Розфарбувати вершини графа таким чином, щоб суміжні вершини мали різні кольори.

Знаходити найкоротший шлях між усіма парами вершин.

Поступово додавати до дерева ребра з найменшою вагою, уникаючи циклів.

Починати з довільної вершини, додавати сусідні вершини з найменшою вагою ребра.

Сортувати всі ребра за спаданням ваги та додавати їх до дерева по черзі.

Алгоритм Прима находити всі мінімальні остовні дерева, а алгоритм Крускала – тільки одне.

Алгоритм Прима завжди будує мінімальне остовне дерево, а алгоритм Крускала – не завжди.

Алгоритм Пріма працює тільки для зважених графів, а алгоритм Крускала – для будь-яких графів.

Алгоритм Прима починає з довільної вершини, а алгоритм Крускала – з найменшого ребра.

Алгоритм Прима використовує структуру черги з пріоритетами, а алгоритм Крускала – ліс.