Лекція 10. Представлення графа. Вершини. Ребра. Орієнтовані та неорієнтовані графи. Список суміжних вершин. Матриця суміжності. Пошук в ширину та в глибину. Дерева пошуку

Дізнаємось

Що таке граф, вершина і ребро.
У чому полягає різниця між орієнтованими та неорієнтованими графами.
Які існують способи представлення графів у програмі.
Як реалізувати список суміжних вершин і матрицю суміжності.
Як працюють алгоритми пошуку в глибину (DFS) і пошуку в ширину (BFS).
Що таке дерево пошуку і як воно формується під час обходу графа.

Навчимось

Створювати та представляти графи у Python різними способами.
Реалізовувати обходи графа — пошук у глибину та пошук у ширину.
Будувати дерева пошуку за результатами обходів.
Аналізувати структуру графа та шляхи між вершинами.
Застосовувати алгоритми обходу для вирішення практичних задач: пошук шляху, перевірка зв’язності, планування процесів.

Проблемні питання

Д.з.

Доступно тільки для зареєстрованих користувачів