АЛГОРИТМЫ НА ГРАФАХ

Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра автоматизации обработки информации (АОИ)










АЛГОРИТМЫ НА ГРАФАХ

Отчет по учебной практике



















Студент гр. 423-2
________________ Р.Р.

17.07.2014
Руководитель
ст. преподаватель каф. АОИ
________________ Н.В.
«___» _______2014









2014
Оглавление
Оглавление 2
1. Введение 2
2. Основные определения 2
3. Алгоритм работы программы 2
4. Структура программы 2
5. Руководство пользователя 2
6. Тестирование программы 2
7. Заключение 2
8. Список использованных источников 2

















1. Введение
Задача практики: создание графического приложения, реализующего построение остова для заданного неорграфа, используя алгоритм ближайшего соседа.Необходимо предусмотреть возможность ввода характеристик графа.
Цель работы: получение практических навыков программирования
Область применения разрабатываемой проблемы: разработка учебногоприложения для решения задач из курса дискретной математики
Техническое значение: программа будет написана с максимальной портируемостью – т.е. с минимальным использованием платформо-зависимых решений. Для этого при написании программы будут использоваться такие библиотеки как SFML, SFGUI и THOR.


















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

Для выполнения задания необходимо определить несколько базовых понятий из теории графов:
Неориентированный граф (неорграф)— это граф, рёбрам которого не присвоено направление. В таком графе не может быть петель. А между двумя вершинами может быть 0 или 1 ребро.
Матрица весов неориентированного графа— это квадратная матрица A размера n, в которой значение элемента aij равно весу ребра из i-й вершины графа в j-ю вершину.
Остов графа — это подграф данного графа, содержащий все его вершины и являющийся деревом (связный граф, не содержащий циклов)
Минимальное остовное дерево— это остов графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

1 2 3 4 5 6
1 0 3 0 6 0 0
2 3 0 4 0 0 0
3 0 4 0 0 0 0
1 6 0 0 0 7 0
5 0 0 0 7 0 2
6 0 0 0 0 2 0

Минимальное остовное дерево и его матрица весов (рис. 1, 2).



3. Алгоритм работы программы

Входные данные: матрица А размерности NxN—матрица весов графа из Nэлементов.
• Проверка графа на необходимые признаки
1. Если N = 0, или матрица не является квадратной, вы получите сообщение об ошибке, иначе продолжится выполнение.
2. Если граф создавался в режиме редактирования вручную, то дополнительно проверяется, задан ли вес для каждого ребра.
3. Выясняется, все ли вершины являются связными. Если все условия выполнены, то начинается выполнение основного алгоритма.
• Поиск минимального остовного деревас использованием алгоритма ближайшего соседа
1. V—пустой массив ребер остовного дерева
2. E—пустой массив вершин графа
3. A—произвольная вершина графа, выбранная случайно или пользователем.
4. Добавляем A в массив E
5. Пока размер Eне равен количеству вершин графа
5.1 Для всех вершин из E сравнить вес ребер,найти ребро минимального веса.
5.2 Если для найденного ребра в Eесть только одна его вершина, добавить его в V и добавить в массив Eвторую его вершину, иначе продолжить поиск, не учитывая данное ребро.
6. Конец цикла.
7. Начать визуализацию алгоритма, выделяя цветом ребра в порядке добавления их в V.
8. Раскрасить все ребра, принадлежащие остову одним цветом, а не принадлежащие—другим.

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

Структуру программы можно представить следующим образом:














Графическое изображение структуры программы (рис. 3).

Система ввода– система, обрабатывающая нажатия на клавиатуру, ввод текста и изменения состояния таких манипуляторовкак мышь.
Интерфейс – система, являющаяся прослойкой между взаимодействующими частями программы: принимает и обрабатывает сигналы системы ввода, переадресовывая полученную информацию другим системам в подходящем виде.
Система вывода– система, отвечающая за реализацию графического интерфейса и визуализацию графа.
Вычислить – функция, запуска алгоритма для обработки информации из матрицы смежности графаи построения минимального остового дерева с последующей визуализацией процесса.
Редактировать – функция, вызывающая режим редактирования графа, позволяющий создать граф вручную, или изменить уже загруженный.
Добавить вершину – функция добавления новой вершины в граф.
Добавить ребро – функция добавления нового ребра в граф.
Задать вес – функция задания веса для ребра графа.
Удалить вершину – функция удаления вершины из графа.
Удалить ребро – функция удаления ребра из графа.
Перестроить – функция, генерирующая заново визуальное представление графа (изменяет позицию вершин).
Очистить – функция создания нового файлас удалением текущего графа.
Сменить язык – функция, позволяющая переключить язык графического интерфейса с русского на английский и наоборот.
Загрузить – функция, загружающая матрицу весов графа из файла, заданного пользователем.
Сохранить – функция, сохраняющая текущий граф в новый файлна диске пользователя.
Выход – выход из программы.








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

После запуска программы для пользователя доступно два способа задания графа: ручной ввод и ввод из существующего файла.
Чтобы ввести граф вручную, нажмите на кнопку редактировать, расположенную на основной (верхней) панели экрана. После этого программа войдет в режим редактирования, и под основной панелью откроется панель редактирования. В нем доступно несколько внутренних режимов:
1. Чтобы перейти в режим добавления вершин, нажмите на прямоугольник слева от надписи “Установка вершин”. После этого вы сможете добавить новую вершину, нажав левой кнопкой мыши в области экрана, не занятой графическим интерфейсом.
2. Чтобы перейти в режим добавления ребер, нажмите на прямоугольник слева от надписи “Установка ребер”. После этого вы сможете добавить новое ребро, последовательно выбрав две вершины. Выбор происходит посредством нажатия на вершину левой кнопкой мыши и сопровождается появлением зеленой подсветки вокруг объекта.
После создания ребра открывается окно изменения веса ребра. Введите неотрицательное число и нажмите ENTER, чтобы изменить вес. Окно изменения веса ребра вы можете вызвать в любое время, пока вы находитесь в режиме редактирования. Для этого произведите двойной щелчок левой кнопкой мыши в области ребра.
3. Чтобы перейти в режим выбора объектов, нажмите на прямоугольник слева от надписи “Выбор объектов”. В режиме выбора объектов, вы не можете создавать новые объекты, однако можете выбирать и удалять уже созданные. Выбор объекта производится нажатием на него левой кнопкой мыши и сопровождается появлением зеленой подсветки вокруг объекта. Удаление объекта происходит по нажатию клавиши DELETE.
Чтобы загрузить граф из уже существующего файла, нажмите на кнопку “Загрузить”, расположенную на основной панели экрана. После этого откроется окно со строкой ввода имени файла. Введите имя файла отдельно или вместе с расширением. Загружаемый файл должен находиться в корневой папке программы, рядом с запускаемым файлом.
Чтобы построить минимальное остовное дерево нажмите на кнопку “Вычислить”, расположенную на основной панели экрана. По прошествии некоторого времени начнется процесс визуализации алгоритма ближайшего соседа. Вершины и ребра будут последовательно подсвечены зеленым цветом, яркая подсветка означает, что объект выбран на данном шаге, темная–на прошедшем. По окончанию работы алгоритма ребра графа, вошедшие в остов, будут окрашены в зеленый цвет, а не вошедшие – в красный.
Чтобы сохранить текущий граф в файл, нажмите на кнопку “Сохранить”, расположенную на основной панели экрана.После этого откроется окно со строкой ввода имени файла. Введите имя файла, под которым вы хотите сохранить матрицу весов текущего графа.
Чтобы очистить экран и создать новый граф, нажмите на кнопку “Новый файл”, расположенную на основной панели экрана. Эта кнопка автоматически включает режим редактирования.
Чтобы изменить визуальное представление графа (позицию вершин графа, возможные пересечения ребер), нажмите на кнопку “Перестроить”, расположенную на основной панели экрана. ВАЖНО!Этот процесс является ресурсоемким и может занимать долгое время, если граф задавался вручную, и было создано большое количество вершин и ребер.
Чтобы изменить языкграфического интерфейсапрограммы, нажмите на кнопку слева от надписи “Язык”, расположенную на основной панели экрана. После этого откроется список доступных языков. Выберите необходимый язык нажатием левой кнопки мыши.
6. Тестирование программы


Вид окна программы при запуске (рис. 4).
Теперь рассмотрим процесс работы программы от начала и до конца на конкретном примере.
При запуске вы увидите окно приветствия. Закройте его нажатием на кнопку продолжить, или нажатием ESCAPEили ENTERна клавиатуре.
Для начала загрузим граф из файла “matrix.txt“, который находится в папке с программой. Нажмите на кнопку “Загрузить” на верхней панели экрана. В появившемся окне введите название файла и нажимаем ENTER.


Окно загрузки файла (рис. 5).
После загрузки вы увидите изображение графа (оно может отличаться от показанного на рисунке ниже). Чтобы получить другое изображение, нажмите на кнопку “Перестроить”, расположенную в верхней части экрана.

Вид загруженного графа (рис. 6).
Теперь зайдем в режим редактирования. Нажмите на кнопку “Редактировать” на верхней панели экрана. На появившейся панели выберите режим установки вершин, щелкнув левой кнопкой мыши в соответствующий прямоугольник.

Режим редактирования (рис. 7).
Добавим несколько новых вершин. Нажмите в любую точку экрана, вокруг нее образуется вершина.Для данного примера достаточно двух вершин.
Теперь выберите режим установки ребер. Чтобы установить ребро, последовательно выберите две вершины графа. Выбрать объект можно нажав на него левой кнопкой мыши. В появившемся окне редактирования веса для каждого добавленного ребра укажите вес. В данном примере хватит четырех дополнительных ребер.

Добавленные вершины (рис. 8).

Процесс добавления ребер (рис. 9).


Финальная версия графа будет выглядеть следующим образом:

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




Результат работы алгоритма (рис. 11).














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












8. Список использованных источников
1. http://en.wikipedia.org/wiki/Undirected_graph
2. http://en.wikipedia.org/wiki/Adjacency_matrix
3. http://en.wikipedia.org/wiki/Minimum_spanning_tree
4. http://algs4.cs.princeton.edu/43mst/
5. http://cgm.cs.mcgill.ca/~soss/cs644/projects/siourbas/sect5.html