Лабораторная работа №22. Решение задач, реализуемых с помощью алгоритмов в графе.

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

Порядок выполнения работы

1. Поиск в ширину.

1. Изучить алгоритм поиска в ширину.

2. Придумать самостоятельно граф для организации поиска в ширину (изобразить его графически). Далее для графа построить матрицу смежности.

3. Реализовать алгоритм поиска в ширину для конкретного графа ( смотри программу 1). . Предусмотреть возможные варианты ответа.( есть маршрут и нет маршрута).

4. При оформлении отчета кратко описать алгоритм поиска, привести пример ручного выполнения алгоритма на примере вашего индивидуального задания, в программе использовать краткие комментарии.

2. Поиск в глубину ( исчерпывающий поиск с возвратом)

1. Изучить алгоритм поиска в глубину.

2. Рассмотреть задачи по теме лабиринт Реализовать алгоритм поиска в глубину для заданного графа, предварительно задать граф матрицей смежности ( смотри программу 2).

3. Также программным способом проверить есть ли путь из точки А в В для второго лабиринта.

4. При оформлении отчета кратко описать алгоритм поиска в глубину, привести пример ручного выполнения алгоритма на примере вашего индивидуального задания, в программе использовать краткие комментарии.

3. Поиск кратчайших путей в графе (Алгоритм Дейкстры)

5. Изучить алгоритм поиска кратчайших путей в графе.

6. Реализовать алгоритм поиска кратчайших путей в графе для заданного графа (смотри задачу 1)предварительно задать граф матрицей смежности (смотри программу 4).

7. Также программным способом проверить есть ли путь из точки А в В для второго лабиринта.

8. При оформлении отчета кратко описать алгоритм поиска в глубину, привести пример ручного выполнения алгоритма на примере вашего индивидуального задания, в программе использовать краткие комментарии.

4. Поиск эйлеровых путей в графе

1. Изучить краткие теоретические сведения об эйлеровых графах. Разобраться в решении задачи об Кенигсберских мостах. Используя полученные сведения решить задачу 1.

2. Реализовать алгоритм поиска эйлерова пути в графе ( смотри программу 3). Придумать граф, задать его матрицей смежности.

3. При оформлении отчета кратко описать алгоритм поиска эйлеровых путей в графе, привести пример ручного выполнения алгоритма на примере вашего индивидуального задания, в программе использовать краткие комментарии.

1. Лабиринт.

Рассмотрим задачу о поиске выхода из лабиринта, коридоры которого не обязательно находятся на одном уровне. Подобная ситуация возникает, например, при блуждании в пещерах или катакомбах.

Отождествив коридоры лабиринта с ребрами, а перекрестки, тупики, входы и выходы - с вершинами, мы придем к связному графу, представляющему схему лабиринта. На рис изображен интересный пример лабиринта в саду Хемптон Корт: Построим соответствующий ему граф.

Рис 1.

Задание 1. Нарисуйте граф, соответствующий лабиринту на рис 2. Найдите путь, по которому можно пройти от пункта А до В лабиринта, используя алгоритм поиска в глубину.

Рис. 2.