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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Алгоритмы на графах

Информация:

Тип работы: курсовая работа. Добавлен: 26.11.2012. Сдан: 2012. Страниц: 20. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Министерство  образования и науки
Государственное образовательное учреждение
высшего профессионального образования
 
Тульский  государственный университет
Кафедра «Электронных вычислительных машин»
 
 
 
Алгоритмы на графах
 
 
 
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к контрольно-курсовой работе по дисциплине
«Методы программирования»
 
 
 
 
 
 
Автор работы:   студент гр. 230791 Чернов Денис Владимирович
Руководитель  работы: доц. кафедры ЭВМ Басалова Г.В.
Работа  защищена: ______________ оценка _________________
 
 
 
 
Тула 2011
Оглавление
 
Введение 3
1. Основные сведения о матрицах смежности. 4
2. Математические зависимости для определения заданных свойств графа 5
2.1. Основные определения. 5
2.2. Алгоритм Прима «Построения минимального остовного дерева» 6
2.3. Алгоритм Дейкстры «Нахождение минимального пути» 10
3. Структура программы 14
3.1 Хранение информации о графе 15
3.2 Входные и выходные данные 15
3.3 Анализ программы 17
4. Руководство пользователя 23
Заключение 25
Список литературы 26
Приложение А 27
Схема программной реализации алгоритма Дейкстры 27
Схема программной реализации алгоритма Прима 28
Приложение Б 29
Листинг программы 29
 


Введение

Контрольно-курсовой проект предназначен для реализации алгоритмов на языках программирования высокого уровня, выбирая структуры  данных для хранения информации, написания  и отладки  программ, реализующих  алгоритмы исследования графов.
Курсовой  проект выполняется с целью закрепления  знаний по курсу «Методы программирования»  и развития навыков самостоятельного проектирования алгоритмов и программ.
Задачами  курсового проекта являются:
    изучение структур хранения графов в ЭВМ
    изучение основных свойств графов 
    оформления и выпуска проектной документации в соответствии с ГОСТ.
Графом  называется алгоритмическая модель, состоящая из множества вершин (узлов) v и соединяющих их ребер e. Ребро - неупорядоченная пара вершин графа. Ребра называются смежными, если они имеют общую вершину. Вершины называются смежными, если есть ребро их соединяющее. Ребро, которое соединяет вершины, называется инцидентным этим вершинам, а вершины – инцидентные этому ребру.
Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике  и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.
Исходные  данные к курсовому проекту:
Способ представления  графа в ЭВМ:
    Матрица смежности.
Перечень  свойств графа, которые необходимо определить:
    Определить минимальное остовное дерево графа.
    Определить минимальный путь между заданными вершинами.

    Основные  сведения о матрицах смежности.


Матрицей смежности графа   с множеством вершин     (соответствующей данной нумерации вершин) называется матрица   размера  , в которой элемент   равен числу ребер в  , соединяющих   и  . Можно получить несколько различных матриц смежности данного графа, меняя обозначения его вершин. Это приведет к изменению порядка строк и столбцов матрицы  . Но в результате всегда получится симметричная матрица из неотрицательных целых чисел, обладающая тем свойством, что сумма чисел в любой строке или столбце равна степени соответствующей вершины. Каждая петля учитывается в степени вершины один раз. Обратно, по любой заданной симметричной матрице из неотрицательных целых чисел легко построить граф, единственный с точностью до изоморфизма, для которого данная матрица является матрицей смежности.  
Если  в клетке i,j установлено значение ПУСТО, то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Иначе дуга есть. Чаще всего за значение ПУСТО берут 0, а в клетки, которые обозначают наличие дуги, вписывают вес этой дуги. Если граф не взвешенный, то вес дуги считается равным единице.
        
Рис.1 Невзвешенный граф G и его матрица смежности
         
Рис.2 Взвешенный граф G и его матрица смежности
 
Матрица смежности является основной структурой данных, которая используется для представления графов в компьютерных программах.
Использование матрицы смежности предпочтительно  только в случае неразрежённых графов, с большим числом ребёр, так как она требует хранения по одному биту данных для каждого элемента.
Разрежённым называется граф, в котором множество рёбер значительно больше квадрата множества вершин.
  Если граф разрежён, то большая  часть памяти напрасно будет  тратиться на хранение нулей,  зато в случае неразрежённых графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно (n^2)/8 байт памяти, что может быть на порядок лучше списков смежности.

    Математические  зависимости для определения  заданных свойств графа


      Основные  определения.


 
Неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
      V это непустое множество вершин или узлов,
      E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.
 
Путь в графе G =(V,E) последовательность вершин   при  , таких, что две любые последовательные вершины соединены хотя бы одной дугой из E.
Число k рёбер в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном.
 
Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
 
В ходе выполнения курсовой работы были проанализированы некоторые из алгоритмов работы с графами. В результате, для  реализации, были выбраны следующие  алгоритмы:
    Для построения минимального остовного дерева во взвешенном графе – алгоритм Прима
    Для нахождения минимального пути между двумя заданными вершинами во взвешенном графе – алгоритм Дейкстры.

      Алгоритм  Прима «Построения минимального остовного дерева»


 
Остовное дерево связного неориентированного графа — ациклический связный подграф данного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрами, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.
Свойства остовных деревьев:
      Любое остовное дерево в графе с n вершинами содержит ровно n ? 1 ребро.
      Число остовных деревьев в полном графе на n вершинах выражается формулой Кэли:
      В общем случае, число остовных деревьев в произвольном графе может быть вычислено при помощи так называемой матричной теоремы о деревьях.
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
                         
Рис.3 Минимальное остовное дерево некоторого графа G
 
Свойства минимальных остовов
      Минимальный остов единственен, если веса всех рёбер различны. В противном случае, может существовать несколько минимальных остовов (какой именно будет выбран алгоритмом Прима, зависит от порядка просмотра рёбер/вершин с одинаковыми весами/указателями)
      Минимальный остов также является остовом, минимальным по произведению всех рёбер (предполагается, что все веса положительны). В самом деле, если мы заменим веса всех рёбер на их логарифмы, то легко заметить, что в работе алгоритма ничего не изменится, и будут найдены те же самые рёбра.
      Минимальный остов является остовом с минимальным весом самого тяжёлого ребра.
      Критерий минимальности остова: остов является минимальным тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра. В самом деле, если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом (добавив это ребро в остов, и удалив самое тяжелое ребро из цикла). Если же это условие не выполнилось ни для одного ребра, то все эти рёбра не улучшают вес остова при их добавлении.
Алгоритм Прима
Этот  алгоритм назван в честь американского  математика Роберта Прима (Robert Prim), который открыл этот алгоритм в 1957 г. Впрочем, ещё в 1930 г. этот алгоритм был открыт чешским математиком Войтеком Ярником (Vojtech Jarnik). Кроме того, Эдгар Дейкстра (Edsger Dijkstra) в 1959 г. также изобрёл этот алгоритм, независимо от них.
Описание алгоритма
Сам алгоритм имеет очень простой вид. Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое,   ребро).
В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется  меньше  ).
Вот как выглядит общий алгоритм построения минимального остовного дерева в псевдокоде:
MST-GENERIC (G, w)
1: A < 0
2: while (пока) A не является остовом
3: do найти безопасное ребро (u, v) ? E для A
4: A < A ? {(u, v)}
5: return A
 
Доказательство
Пусть граф   был связным, т.е. ответ существует. Обозначим через   остов, найденный алгоритмом Прима, а через   — минимальный остов. Очевидно, что  действительно является остовом (т.е. поддеревом графа  ). Покажем, что веса   и   совпадают.
Рассмотрим  первый момент времени, когда в   происходило добавление ребра, не входящего в оптимальный остов  . Обозначим это ребро через  , концы его — через   и  , а множество входящих на тот момент в остов вершин — через   (согласно алгоритму,  ,  , либо наоборот). В оптимальном остове  вершины   и   соединяются каким-то путём  ; найдём в этом пути любое ребро  , один конец которого лежит в  , а другой — нет. Поскольку алгоритм Прима выбрал ребро   вместо ребра  , то это значит, что вес ребра   больше либо равен весу ребра  .
Удалим  теперь из   ребро  , и добавим ребро  . По только что сказанному, вес остова в результате не мог увеличиться (уменьшиться он тоже не мог, поскольку  было оптимальным). Кроме того,   не перестало быть остовом (в том, что связность не нарушилась, нетрудно убедиться: мы замкнули путь   в цикл, и потом удалили из этого цикла одно ребро).
Итак, мы показали, что можно выбрать  оптимальный остов   таким образом, что он будет включать ребро  . Повторяя эту процедуру необходимое число раз, мы получаем, что можно выбрать оптимальный остов   так, чтобы он совпадал с  . Следовательно, вес построенного алгоритмом Прима   минимален, что и требовалось доказать.

      Алгоритм  Дейкстры «Нахождение минимального пути»


 
Пусть задан простой неориентированный  граф G = (V, E), как конечное множество  вершин V и множество E неупорядоченных  пар {vi, vj} – ребер. Каждому ребру предписано действительное число a[i][j] > 0, которое называется длиной этого ребра. Требуется найти кратчайший путь между заданными вершинами s и q, то есть такую последовательность вершин u1,u2,…,un, что u1=s, un=q, {ui, ui+1}IE для всех 1 ? i ? n-1, и сумма длин ребер {ui, ui+1} минимальна. Задача решается с помощью алгоритма Дейкстры:
    Каждой вершине припишем временный вес t (vi) = ?. Положим t (s) = 0 и далее t (s) изменяться не будет, т.е. t (s) – постоянный вес вершины s. Положим v = s.
    Для всех вершин u = vi, смежных с v, имеющих временный вес, изменяем вес по формуле .
    Устанавливаем постоянный вес той вершины u, которая имеет наименьший временный вес. Положим v = u. Если v = q, то t (v) – длина кратчайшего пути из s в q. Если v ? q, то переходим к шагу 2.
В результате работы алгоритма получим  длину кратчайшего пути из s в q. Чтобы  найти вершину и ребра, составляющие этот путь, нужно определить массив h[|V|], где h[v] – вершина, предшествующая вершине v на кратчайшем пути, а в  шаге 2 добавить операцию h[u] = v, в случае, когда t (u) > t (v)+a[v][u].
Можно получить кратчайшие пути от s ко всем другим вершинам, изменив условие  остановки. Вычисления заканчиваются, когда все веса становятся постоянными.
В тексте программы веса вершин записываются в массив t [ ]. Для обозначения того, что для вершины v вес t [v] постоянный, вводится массив x[ ]. Равенство x[v]=1 будет означать, что t [v] – постоянный вес.
Вот как выглядит общий алгоритм нахождения минимального расстояния между двумя заданными вершинами в псевдокоде:
1: 
2:Для всех   отличных от a
3:присвоим 
4:Пока 
5:Пусть   — вершина с минимальным d[v]
6:Для всех   таких, что 
7:если d[u] > d[v] + w[vu] то
8:изменим 
9:изменим 
Обозначения:
V — множество вершин графа
E — множество ребер графа
w[ij] — вес (длина) ребра ij
a — вершина, расстояния от которой ищутся
U — множество посещенных вершин
d[u] — по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u
p[u] — по окончании работы алгоритма содержит кратчайший путь из a в u
 
Доказательство того, что вышеприведенный  алгоритм действительно дает кратчайшие пути.
Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S1 – множество вершин с этими пометками, а S2 – множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(xi) дает кратчайший путь от s к xi, проходящий полностью по вершинам множества S1. (Так как при каждой итерации во множество S1 включается только одна вершина, то обновление пометки l(xi) требует только одного сравнения на шаге 2.)
Пусть кратчайший путь от s к xi* не проходит целиком по S1 и содержит по крайней мере одну вершину из S2, и пусть xj S2 – первая такая вершина в этом пути. Так как по предположению cij неотрицательны, то часть пути от xj к xi* должна иметь неотрицательный вес   и . Это, однако, противоречит утверждению, что l(xi*) – наименьшая временная пометка, и, следовательно, кратчайший путь к xi* проходит полностью по вершинам множества S1, и поэтому l(xi*) является его длиной.
Так как вначале множество S1 равно (s) при каждой итерации к S1 добавляется xi*, то предположение, что l(xi*) равно длине кратчайшего пути  xi S1, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.
Если  требуется найти кратчайшие пути между s и всеми другими вершинами  полного связного графа с n вершинами, то в процессе работы алгоритма выполняются  операций сложения и сравнения на шаге 2 и еще   операций сравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины временные, а для этого нужно еще   операций сравнения. Эти величины являются верхними границами для числа операций, необходимых при отыскании кратчайшего пути между заданными вершинами s и t. Они действительно достигаются, если окажется, что вершина t будет последней вершиной, получившей постоянную пометку.
Как только длины кратчайших путей от s будут найдены (они будут заключительными  значениями пометок вершин), сами пути можно получить при помощи рекурсивной  процедуры с использованием соотношения (*). Так как вершина xi' непосредственно предшествует вершине xi в кратчайшем пути от s к xi, то для любой вершины xi соответствующую вершину xi' можно найти как одну из оставшихся вершин, для которой
' ' . (*)
Если  кратчайший путь от s до любой вершины  xi является единственным, то дуги (xi', xi) этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько «кратчайших» путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине xi' соотношение (*) будет выполняться для более чем одной вершины xi. В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между s и xi), либо таким, что рассматриваются все дуги (xi', xi), входящие в какой-либо из кратчайших путей и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительно s или кратко – s-базой.
 

    Структура программы


 
Проект  выполнен в среде разработки C++ Builder 2009 и называется KursGraths. Он содержит одну (главную) форму с расположенными на ней обработчиками событий (controls). Описание основных пользовательских типов и переменных, используемых в каждом конкретном обработчике вынесены в его начало. В таблице, приведенной ниже, описаны основные функции каждого из обработчиков событий главного модуля.
    Имя обработчика
   Название контрола
          Функции
TForm3
Курсовая работа: Графы. Выполнил Чернов Денис гр.230791
Здесь описано окно программы, которое видит пользователь сразу  после ее запуска. Размещены процедуры импорта графа, вывода графа на экран, кнопки определения свойств графа, кнопки очистки полей изображений, печати заданного графа, кнопка вызова справки.
TButton1
Печать
Отправка графа на печать принтеру (Виртуальному или физическому)
TButton2
Открыть
Импорт матрицы смежности  из файла
TButton3
Справка
Вызов файла help.txt
TButton4
Минимальный остов
Процедура построения минимального остовного дерева для импортированого графа
TButton5
Clear All
Очищает первую картинку с графом
TButton6
Clear All
Очищает вторую картинку с графом
TButton7
Кратчайший путь
Процедура нахождения минимального расстояния между двумя задаными вершинами в импортированом графе
Edit4
Начальная вершина
Поле ввода начальной  вершины
Edit5
Конечная вершина
Поле ввода конечной вершины
Image1
Граф1
Форма для рисования графа (для определения кратчайшего  пути)
Image2
Граф2
Форма для рисования графа (для определения минимального остовного дерева)

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

3.1 Хранение информации  о графе

 
По умолчанию  тип всех данных, используемых в  программе – int.
    a [i][j] – динамический массив содержащий матрицу смежности графа
    mas [3][20] – массив содержащий информацию о пройденных вершинах (используется при построении МОД).
    x[6] Массив, содержащий единицы и нули для каждой вершины,
(x[i]=0 - еще  не найден кратчайший путь  в i-ю вершину, x[i]=1 - кратчайший  путь в i-ю вершину уже найден).
 
    x1[20] – Массив координат по оси Х (Для расположения вершин по окружности)
    у1[20] – Массив координат по оси У (Для расположения вершин по окружности)
 

3.2 Входные и  выходные данные

 
Входные данные поступают в программу  при импорте текстового файла  с расширением .txt название импортируемого файла может быть произвольным. Внутри открываемого текстового файла, в первой строчке должно содержаться число, которое показывает количество вершин графа. Со второй строчке в файле должна быть занесена матрица смежности графа, каждая цифра отделяется от предыдущей пробелом.
6
0 0 0 0 0 9
0 0 5 0 0 0
0 5 0 20 0 7
0 0 20 0 8 1
0 0 0 8 0 1
9 0 7 1 1 0 
Рис.4 Пример входного файла gr.txt
 
Выходные  данные формируются в виде изображения. В случае нахождения минимального остова, в конце работы программы, построенный  остов  подсвечивается зелёным цветом. В случае нахождения минимального пути алгоритмом Дейкстры, минимальный путь между двумя указанными вершинами также подсвечивается зелёным цветом. Рассмотрим матрицу смежности отраженную на Рис.4, для такой матрицы смежности выходными данными будут являться изображения:
Минимальное расстояние между вершинами 2 и 4:
Рис.5 Пример определения  минимального расстояния
 
Минимальное остовное дерево для графа, заданного на Рис.4:
Рис.6 Пример построенного минимального дерева

3.3 Анализ программы

 
Ниже  мы рассмотрим основные функции, использованные в нашей программе, при реализации алгоритмов на графах:
 
void __fastcall TForm3::Button2Click(TObject *Sender) {}
При вызове этой функции открывается  диалоговое окно для выбора текстового файла с матрицей смежности.  Компонент OpenDialog1 вызывает диалоги в зависимости от выбранного файла присваивает переменной name строку с именем файла. Если значение переменной name = NULL выводится ошибка о том что файл не найден.  Далее Также данная функция заполняет матрицу смежности a[][] значениями из открытого файла и строит в компонентах Image1 и Image2 изображение графа. Image1->Canvas->MoveTo – поставить точку, Image1->Canvas->LineTo – построить из точки линию,  Image1->Canvas->TextOutA – вывести текст по заданным координатам,
Image1->Canvas->Ellipse – построить окружность, Image2->Canvas->Pen->Color/Width  – задать
цвет /ширину пера.  Рисование вершин происходит по окружности для расчёта координат рисования вершин были использованы формулы x=w+(130*cos(i*2*3.14/n)) и
y=h+(130*sin(i*2*3.14/n)), где n – число вершин графа, w – ширина окна в котором будет рисоваться граф\2, h – высота окна, в котором будет рисоваться граф\2 (переменные w,h нужны чтобы рисовать граф приблизительно посередине окна).
Входные данные – количество вершин, матрица  смежности.
Выходные  значения – координаты вершин и  смежных им ребер 
 
 
void __fastcall TForm3::Button4Click(TObject *Sender){}
Эта функция создаёт массив mas [3][n] в котором будут храниться номера вершин и минимальные веса смежных с ними ребер. Сначала функция загружает массив a[][] из файла (предполагается, что число вершин графа меньше или равно 20). Переменная k=n-1 отражает свойство минимального дерева, такое что количество ребер в МОД на единицу меньше  чем число вершин. Этот массив инициализируется: каждому a[i] [j] присваивается 1000 (предполагается, что максимальная длина ребра меньше 1000). Потом данные из матрицы смежности копируются в массив. При этом если в выбранном текстовом файле ничего не содержится в массив ничего не копируется. Затем делается цикл, который прерывается только тогда, когда все элементы массива станут снова равны 1000. Сначала находится минимальный элемент массива (из области выше главной диагонали матрицы ввода). Он запоминается (переменная buf) и ему присваивается 1000. Согласно алгоритму Прима, если ребро подходящее минимальный элемент вычеркивается, а цикл начинается с начала: Создается массив versh[n]. Каждый элемент этого массива равен 1 или 0. Когда вершина включается в дерево, в элемент массива с ее номером записывается 1 (изначально все элементы массива versh[], кроме versh[1] равны 0). Чтобы определить подходящее ребро или нет, нужно посмотреть, находятся ли единицы в массиве (номера элементов равны номерам вершин ребра). Если номерам вершин ребра соответствуют обе единица, значит, ребро не подходящее. Если это условие не выполняется – ребро подходящее. Для этого используем цикл:
for (int i=1; i<n; i++)
for (int j=0; j<i; j++)
{
if ((a[i][j] < buf) && ((versh[i]==1) || (versh[j]==1)) && (versh[i]!=versh[j]))
{buf=a[i][j]; p=i; q=j;}
}
if (versh[p]==1) versh[q]=1; else versh[p]=1;
a[p][q]=1000;
mas[0] [kmas]=p;
mas[1] [kmas]=q;
mas[2] [kmas]=buf;
sum=sum+buf;
kmas++; k--;
}
  Алгоритм прекращает работу, когда  все вершины включены в новый  граф.
Далее функция на основании данных массива  mas[][] строит ребра, включенные в минимальное остовное дерево. Для этого используются циклы:
for (int i=0; i<n; i++)
{
x2[i]=215+(130*cos(i*2*3.14/n));
y2[i]=154+(130*sin(i*2*3.14/n));
}
for (int i=0; i<kmas; i++)
{
Image2->Canvas->MoveTo (x2[mas[1] [i]], y2[mas[1] [i]]);
Image2->Canvas->LineTo (x2[mas[0] [i]], y2[mas[0] [i]]);
}
Где x2[] y2[] – массивы координат по осям x и y соответственно.
ShowMessage("Суммарный вес пути - " + IntToStr(sum))  - функция вывода системных сообщений на экран.
Входные данные – количество вершин, матрица  смежности.
Выходные  значения – координаты вершин и  смежных им ребер составляющих минимальное остовное дерево.
 
void __fastcall TForm3::Button7Click(TObject *Sender){}
В данной функции реализован алгоритм Дейкстры. Переменная buf типа AnsiString используется для хранения вершин, включенных в минимальный маршрут между двумя вершинами. Массив mas[] используется для хранения номеров вершин в ASCII – коде. Переменная infinity по умолчанию равна 1000 (используется для обозначения пути изначально бесконечной длины). n-количество вершин в графе, s – начальная вершина, q-конечная вершина. x[]-массив, содержащий единицы и нули для каждой вершины, (x[i]=0 - еще не найден кратчайший путь в i-ю вершину, x[i]=1 - кратчайший путь в i-ю вершину уже найден), t[] содержит длину кратчайшего пути от вершины s в q, h[i] - вершина, предшествующая i-й вершине. Сначала перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<p;u++)
  {
 if(data[v][u]==0)continue;
 if(x[u]==0 && t[u]>t[v]+data[v][u])
Если  для вершины u еще не найден кратчайший путь, и новый путь в u короче чем  старый, то: запоминаем более короткую длину пути в массив t и запоминаем, что v->u часть кратчайшего пути из s->u
t[u]=t[v]+data[v][u]; 
h[u]=v; 
}
  }
Далее  ищем из всех длин путей самый короткий, переменная w=infinity для поиска самого короткого пути. Следующий цикл перебирает все вершины и // Если для вершины не найден кратчайший путь и если длина пути в вершину u меньше уже найденной, то текущей вершиной становится u-я вершина. Заносим номер этой вершины в edit3.
  for(u=0;u<p;u++)
  {
 if(x[u]==0 && t[u]<w)
{
v=u;
w=t[u];
}
  }
  if(v==-1)
  {
 Application->MessageBox("Указанные вершиниы не имеют ребер", NULL, MB_OK);
 break;
  }
Присваиваем переменной m типа AnsiString строку из edit3.
Следующий цикл используется для занесения  в массив mas номеров вершин включенных в минимальный маршрут:
for(l=1,buf="";l<=m.Length()+1;l++)
{
  if(l==m.Length()+1)
   {
mass[k++] = StrToInt(buf);
break;
   }
  if(m[l]==' ')
   {
mass[k++] = StrToInt(buf);
buf = "";
   }
  buf += m[l];
}
Где m.Length() – длина строки компонента edit3. StrToInt() – функция преобразования текущего значения буфера из типа AnsiString в INT.
Далее, в функции производится построение только тех вершин, которые попали в минимальный маршрут(находятся в массиве mas). Построение реализовано, способом аналогичным предыдущей функции.
Входные данные – количество вершин, матрица  смежности, начальная вершина, конечная вершина.
Выходные  значения – координаты вершин и  смежных им ребер составляющих минимальный маршрут между двумя заданными вершинами.
void __fastcall TForm3::Button5Click(TObject *Sender){}
Функция очистки компонентов Image1, edit3, edit4, edit5.
Image1->Canvas->Pen->Color=clWhite – устанавливаем белый цвет пера
Image1-> Canvas->Brush->Color = clWhite; - устанавливаем белую заливку
Edit5->Clear() – удаляем весь текст из поля ввода edit5
Image1->Canvas->FillRect(Rect(0,0,Image1->Width,Image1->Height)) – рисуем белый прямоугольник по всей площади компонента и заливаем его.
Edit4->Clear() – удаляем весь текст из поля ввода edit4
Edit3->Clear()  – удаляем весь текст из поля ввода edit3
Входные данные  - компоненты Image1, edit4, edit5
Данная  функция не возвращает значений
 
void __fastcall TForm3::Button6Click(TObject *Sender){}
Данная  функция предназначена для очистки  компонента Image2
Image2->Canvas->Pen->Color=clWhite - устанавливаем белый цвет пера
Image2-> Canvas->Brush->Color = clWhite -  устанавливаем белую заливку
Image2->Canvas->FillRect(Rect(0,0,Image1->Width,Image1->Height)) - рисуем белый прямоугольник по всей площади компонента и заливаем его.
Входные данные  - компонент Image2
Данная  функция не возвращает значений
 
void __fastcall TForm3::Button3Click(TObject *Sender){}
Функция предназначена для открытия текстового файла help.docx. используется стандартная  функция
ShellExecute(Handle, "open", "help.docx", NULL, NULL, SW_NORMAL);
 
void __fastcall TForm3::Button1Click(TObject *Sender){}
Объект  класса Tprinter – Prntr соответствует запросу на печать через локальный принтер (установленный на компьютере по умолчанию!!!) Prntr->BeginDoc() – открываем сессию печати.
Prntr->Canvas->Draw(10,10, Image1->Picture->Graphic) –задаём положение картинки на листе и указываем на компонент из которого необходимо напечатать изображение. Prntr->EndDoc() – закрываем сессию печати.
В
 
 
 

    Руководство пользователя


    и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


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