Уроки 47 - 49
Графы. Основные понятия
(§44. Графы)
Содержание урока
Задачи
Задачи
1. Напишите программу, которая вводит из файла весовую матрицу графа и строит для него минимальное остовное дерево.
2. Оцените асимптотическую сложность алгоритма Прима-Крускала.
3. Напишите программу, которая вводит из файла весовую матрицу графа, затем вводит с клавиатуры номера начальной и конечной вершин и определяет кратчайший маршрут.
4. Напишите программу, которая вводит из файла весовую матрицу графа и определяет длины всех кратчайших маршрутов с помощью алгоритма Флойда-Уоршелла.
5. Оцените асимптотическую сложность алгоритмов Дейкстры и Флойда-Уоршелла.
6. Напишите программу, которая решает задачу коммивояжёра для 5 городов методом полного перебора. Можно ли использовать её для 50 городов?
*7. Напишите программу, которая решает задачу 5 (о размещении школы). Для определения кратчайших путей используйте алгоритм Флойда-Уоршелла. Весовую матрицу графа вводите из файла.
Следующая страница 
§44. Графы
Cкачать материалы урока
