Программа реализующая алгоритм обхода графа в глубину сделанная на C++ с пошаговой графической реализацией алгоритма на WinFoms. Чтобы открыть проект требуется VisualStudio 2013 или новее (2017 лучше всего).
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 5
1 ЧТО ТАКОЕ ГРАФ И КАК ЕГО МОЖНО ПРЕДСТВАИТЬ 6
1.1 Основные определения связанные с теорией графов 6
1.2 Способы представления графов 7
1.2.1 Списки смежности и тому подобное 7
1.2.2 Списки дуг 8
1.2.3 Матрица смежности 9
2 ВИДЫ ОБХОДА ГРАФА 11
2.1 Обход графа в ширину 11
2.2 Обход в глубину 14
2.3 Алгоритм Дейкстры 17
3 ОПИСАНИЕ ПРОГРАММЫ 20
ВЫВОДЫ 22
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 23
ПРИЛОЖЕНИЕ А 24
ПРИЛОЖЕНИЕ Б 25
ВЫВОДЫ
В ходе курсовой работы были детально рассмотрены понятия, связанные с теорией графов, а также рассмотрены основные виды представления графов, из которых выбран способ представления, в виде матрицы смежности, это обусловлено тем, что алгоритм обхода в глубину применяется для не ориентированных, не взвешенных графов.
После этого были проанализированы все виды обходов графа и проведена их сравнительная характеристика, которая выявила все преимущества обхода графа в глубину.
Для написания программы был выбран язык С++. Это обусловлено тем, что данный язык самый быстрый в мире высокоуровневый язык программирования. Для языка С++ характерны лаконичность, стандартный набор конструкций управления потоком выполнения, структур данных и обширный набор операций, а также данный язык совместим с выбранным способом визуализации – CLI.
После этого была написанная программа, с помощью которой, пользователь может задать свой собственный граф после чего, при нажатии соответствующей кнопки, произойдет пошаговый обход, заданного графа, в глубину. Данная программа включает в себя разнообразный пользовательский интерфейс состоящий из множества различных кнопок, а также элементов ввода-вывода. Каждая составляющая данного интерфейса была детально проанализирована и объяснена.
psyfaker