Реферат: Графовые модели. Остов минимального веса

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

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

В настоящее время наиболее распространенной средой является Delphi.

Delphi – пакет средств быстрой разработки приложений. К достоинствам относятся удобный интерфейс, высокая скорость работы, большое количество библиотек компонентов, эффективность создаваемых программ. Кроме того, строгая типизированность языка Object Pascal позволяет компилятору уже на этапе компиляции обнаружить многие ошибки, а также возможность работать с указателями.

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

Кроме того, в Delphi имеются развитые средства для работы с графическими возможностями Windows. В стандартном графическом интерфейсе Windows основой для рисования служит дескриптор контекста устройства нос и связанные с ним шрифт, перо и кисть. В состав входят объектно-ориентированные надстройки над последними, назначением которых является удобный доступ к свойствам инструментов и прозрачная для пользователя обработка всех их изменений. Поэтому использование класса TCanvas, являющегося основой графической системы Delphi, позволяет выполнить одну из основных функций разрабатываемой программы – наглядное представление графа. Delphi также дает возможность использовать традиционный набор функций работы с файлами, унаследованный от Turbo Pascal. Что позволяет сохранять результаты работы программы в файлы на жестком диске. Кроме того, в данной среде имеется возможность, наряду с обычными массивами, создавать динамические массивы, которые будут играть роль матрицы весов ребер графа. Хотя по большей части на представление графа в памяти машины выбор инструментальных средств особого значения не имеет.

Программа CorelDRAW 11, составляющая основу современного набора программных средств фирмы Corel, была выпущена в августе 2002 г. Она представляет собой результат двенадцатилетней эволюции, обладает удивительной универсальностью и мощностью, будучи в равной степени полезной и в промышленном дизайне, и в разработке рекламной продукции, и в подготовке публикаций, и в создании изображений для web-страниц, также в создании блок-схем алгоритмов. Несмотря на то, что мировым лидером программ для работы с векторной графикой сегодня является другая программа — Adobe Illustrator, CorelDRAW 11 ни в чем не уступает ей, а по многим параметрам и превосходит, и у нее — огромная армия пользователей-профессионалов, считающих CorelDRAW своим основным рабочим инструментом.

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

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

3 Блок-схема алгоритма задачи моделирования

Рисунок 1.Блок-схема алгоритма задачи моделирования

3.1 Описание блок-схемы алгоритма задачи моделирования

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

Блок 2. Ввод вершины поиска. После заполнения матрицы весов пользователем программа автоматически определяет вершину начала построения остова.

Блок 3. Поиск ребра минимального веса среди инцидентных n ребер. Программа анализирует матрицу весов и находит ребро с минимальным весом. Найденное ребро сохраняется в переменную min.

Блок 4. Формирование остова. Формируется остов.

Блок 5.Выбор новой инцидентной вершины. Помечается новая вершина, инцидентная ребру, - переменная m.

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

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

Блок 8. Инцидентные помеченным вершинам ребра. Если есть такие ребра, то программа анализирует найденные ребра, если нет инцидентных ребер, то программа переходит к Блоку 6.

Блок 9. Ребра остова. Найденное ребро не используется в остове, то программа переходит к Блоку 10, а если используется, то переходит к Блоку 6.

Блок 10. Образует ребро в остове цикл, если да то программа переходит к Блоку 6. Если ребро не образует в остове цикл, то программа переходит к Блоку11.

Блок 11. Нахождение ребра минимального веса. Программа анализирует оставшиеся инцидентные ребра выбранной вершине и переходит к Блоку 12.

Блок 12. Формирование остова. Программа формирует полученный остов, проверяется связанность ребер с вершинами графа, за это отвечает массив связанности ar[jmin, imin], если он равен единицам, то все ребра связаны с вершинами, если он не равен единице, то продолжается формирование остова.

Блок 13. Выбор новой инцидентной вершины. Помечается новая вершина графа, программа переходит к Блоку 6.

Блоки блок-схемы во многом повторяют шаги теоретического решения, лишь незначительно конкретизируясь на привязке к конкретному языку программирования (в данном случае Delphi).

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

4 Операционная среда моделирования