Графы

В данном разделе вы сможете изучить и закрепить:

  • Что такое граф и другие основные определения;
  • Способы задания графа;
  • Пути в графе, связный граф и компоненты связности;
  • Обходы графа, DFS, BFS;
  • Остов, алгоритм Прима, алгоритм Краскала;
  • Алгоритмы Дейкстры, Флойда-Уоршелла;
  • Деревья, кодирование и декодирование Прюфера;
  • Плоские графы;
  • Раскраска графов.

Задание 0Степени вершин, число компонент связности, эйлеровый и двудольный графы

Задание 1Обход графа в глубину

Задание 2Проверка обхода графа в глубину

Задание 3Обход графа в ширину

Задание 4Проверка обхода графа в ширину

Задание 5Число компонент связности

Задание 6Проверка числа компонент связности

Задание 7Построение минимального остового дерева

Задание 8Кратчайшие пути от заданной вершины до остальных

Задание 9Матрица кратчайших путей

Задание 10Кодирование Прюфера

Задание 11Декодирование Прюфера

Задание 12Раскраска графа