Алгоритм Прима C# (C# WinForm Net.Framework 4.5.2)

Курсовой проект

по курсу "Логика и основы алгоритмизации в инженерных задачах"

на тему "Алгоритм Прима"

Содержание

Введение

• Постановка задачи
• Теоретическая часть задания
• Описание алгоритма решения поставленной задачи
• Пример ручного расчета задачи и вычислений
• Описание программы
• Тесты

ЗаключениеСписок литературыЛистинги программы Результат работы программы

Введение

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. В начале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов.

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

Тема данной курсовой является алгоритм Прима – алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева и вершину не из дерева.

Постановка задачи

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

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

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

В качестве среды разработки была выбрана программа MS Visual Studio 2017, а языком программирования – C#. Созданная программа будет ориентирована на операционную систему MS Windows.

Содержимое архива

Содержимое курсовой работы (.rtf) - 30 страниц

Язык : С#, Net.Framework 4.5.2

Исходный код в архиве