Анализ предметной области. Для представления графа в программе была выбрана матрица смежности как самый универсальный способ представления

Для представления графа в программе была выбрана матрица смежности как самый универсальный способ представления. Для корректной работы программы в каталоге, в котором находится программа должен находиться файл с названием “matrix.txt” в котором должна быть представлена матрица смежности графа размерностью 6*6. Возможно размещение в одном файле нескольких матриц, а затем загрузку из файла необходимой матрицы. Пример оформления матриц:

0 6 2 5 0 0

6 0 5 0 3 0

2 5 0 5 1 4

5 0 5 0 0 2

0 3 1 0 0 2

0 0 4 2 2 0

 

0 1 0 1 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 1 0 0 0

0 0 0 0 0 1

0 0 0 0 0 0

 

Реализованные алгоритмы:

1. Поиск самого короткого цикла в графе

Для поиска цикла необходимо сначала избавиться от вершин, которые не задействованы ни в одном цикле графа. Так как вершина, куда только входят или откуда только выходят дуги, точно не будет входить в цикл, ее можно убрать из обработки. В матрице смежности такая вершина будет выглядеть как пустой столбец или пустая строка. Для удаления достаточно сделать нулевой и строку, и столбец, соответствующий вершине. После проведения этих операций у нас остаются только вершины, через которые идет цикл. Если осталась пустая матрица, значит граф является ацикличным.

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

2. Обход графа в глубину

Поиск в глубину является обобщением метода обхода деревьев в прямом порядке. Поиск в глубину начинается с выбора начальной вершины графа, и эта вершина помечается как посещенная. Затем для каждой вершины, смежной с текущей вершиной и ранее не посещенной, рекурсивно применяется поиск в глубину. Когда все вершины, которых можно достичь из текущей, были посещены, поиск заканчивается. Если при этом остались не посещённые вершины, то выбирается одна из них и алгоритм повторяется.

3. Построение минимального остовного дерева по алгоритму Прима

Построение производится с заданной вершины по принципу нахождения минимального веса ребра от текущей вершины. Вершина начальная добавляется в остовное дерево и помечается как “пройденная”. Далее по матрице смежности находится минимальный вес ребра исходящий из этой вершины. Как только он найден следуем по этому ребру в вершину делаем ее текущей и также помечаем как “пройденную”. За тем повторяем весь алгоритм снова до тех пор пока не останется не “пройденных” вершин

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

На первом этапе в массив кратчайших расстояний записывается вес ребра,если таковой существует от заданной вершины до остальных если же прямого пути нет то записывается “бесконечность”. На следующих этапах происходит нахождение пути от заданной вершины через все остальные по формуле: D[v]:=min(D[v],D[w]+C[w,v])

D[1..n]- массив содержащий кротчайшие пути от исходной вершины до остальных

S[]- массив(множество) посещенных вершин

w-добавленная в S вершина

 

Вывод

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Также графы применяются в химии, информатике и программировании, экономике, логистике и схемотехнике.

Во время написания программы мной были изучены и применены на практике алгоритмы реализации графов на языке Pascal. Кроме того, были изучены алгоритмы на графах, как то: поиск самого короткого цикла в графе, поиск в глубину, построение минимального остовного дерева с помощью алгоритма Прима и поиск кратчайшего пути от заданной вершины до остальных по алгоритмы Дейкстры.

Все поставленные задачи были решены, для программы было разработано удобное меню со всеми доступными функциями. Был выбран формат ввода в программу графа – графы хранятся в текстовом файле в виде матрицы смежности. В одном файле допускается хранение любого количества графов, загрузка нужного же производится из программы с помощью процедуры OpenFile, в которой первым аргументом необходимо указать номер матрицы, которую следует загрузить, а вторым – глобальную переменную матрицы, в которую необходимо ввести данные из файла. Такой подход позволяет показать несколько алгоритмов на различных графах, не меняя каждый раз файл с матрицами.

Используемая литература

1. Алексеев В. Е., Таланов В. А. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Бином, 2006.

2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. — М.: Издательский дом «Вильямс», 2001.

3. Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский диалект, 2008.

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с. англ. — М.: Мир, 1982.

5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. – М.: Лаборатория базовых знаний, 2003.

6. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы. – М.: Мир, 1976. – 736 с. (3-е изд.: Уч. пос. – М.: Издательский дом «Вильямс», 2000.

7. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. - М.: Мир, 1978. – 846 с. (2-е изд.: Уч. пос. – М.: Издательский дом «Вильямс», 2000.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.

9. Красиков И. В., Красикова И. Е. Алгоритмы. Просто как дважды два. – М.: Эксмо, 2007.

10. Лэнгсам Й. Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. – М.: Мир, 1989.

11. Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. – Москва: Техносфера, 2004.

12. Окулов С. М. Программирование в алгоритмах. – 2-е изд., доп. – М.: БИНОМ. Лаборатория знаний, 2006.

13. Таха Х. Введение в исследование операций. — М.: Издательский дом «Вильямс», 2001.

14. Ускова О.Ф. и др. Программирование алгоритмов обработки данных: Учебное пособие. – СПб: БХВ-Петербург, 2003.