Занятие №4 «Элементарные алгоритмы для работы с графами. Представление графов»

ЗАДАНИЕ:

Разработать программу на языке С++ (Python, Java), которая:

- запрашивает пользователя о количестве вершин и ребер взвешенного неориентированного графа, а также перечень существующих ребер и их вес;
- формирует по полученной информации матрицу смежности графа;
- запрашивает начальную и конечную вершину графа;
- выводит на экран кратчайший путь между заданными вершинами и его вес; - проверить на примере графа:

Задачу решить с помощью алгоритма Дейкстры и алгоритма Флойда. Сравнить их эффективность.


Контрольные вопросы:

1. 
   С какими видами графов работают алгоритмы Дейкстры, Флойда и переборные алгоритмы?
   
2. 
   Как от представления графа зависит эффективность алгоритма его обхода?
   
3. 
   За счет чего поиск в ширину является достаточно ресурсоемким алгоритмом?
   
4. 
   В чем преимущества алгоритмов обхода графа в ширину?
   
5. 
   Каким образом в алгоритме перебора с возвратом при обходе графа обрабатывается посещение тупиковых вершин?
   
6. 
   Поясните на примере обхода графа этап обратного хода в волновом алгоритме. Почему его удобно выполнять с конца?
   
7. 
   При программной реализации алгоритмов обхода графа с помощью рекурсии что выделяется в качестве базы и как организована декомпозиция?
   

Список литературы:
1. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн; пер. с англ. – 2-е изд. – М.: Вильямс, 2011. – 1 296 с.
2. Кристофидес, Н. Теория графов: Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978. – 434 с.
3. Седжвик, Р. Фундаментальные алгоритмы на С++: Алгоритмы на графах / Р. Седжвик; пер. с англ. – СПб.: Диасофт, 2002. – 496 с.
4. Скиена, С. Алгоритмы. Руководство по разработке / С. Скиена; пер. с англ. – 2-е изд. – СПб.: БХВ-Петербург, 2011.– 720 с.
5. Троелсен, Э. С# и платформа .NET 3.0, специальное издание / Э. Троелсен. – СПб.: Питер, 2008. – 1 456 с.