Поиск пути в ориентированном графе

Раздел
Программирование
Предмет
Просмотров
596
Покупок
0
Антиплагиат
Не указан
Размещена
29 Сен 2012 в 15:17
ВУЗ
Не указан
Курс
Не указан
Стоимость
2 000 ₽
Демо-файлы   
1
zip
Отчет_Демо.doc Отчет_Демо.doc
1011.9 Кбайт 1011.9 Кбайт
Файлы работы   
1
Каждая работа проверяется на плагиат, на момент публикации уникальность составляет не менее 40% по системе проверки eTXT.
rar
Kursovik_GRAF
1.8 Мбайт 2 000 ₽
Описание
Программа написана на Delphi 7. Занимается поиском путей в орграфе.
Программа реализует поиск путей в орграфе, характеризуется следующими параметрами:
• поиск кратчайшего пути;
• поиск пути наибольшей длины;
• нахождение длин кратчайшего и пути наибольшей длины;
• вычисление количества простых путей;
• визуализация данных процессов


- Входные данные:
• количество вершин графа;
• матрица весов (длин);
• начальная, конечная вершины.
- Выходные данные:
• количество простых путей;
• кратчайший путь. Его длина;
• путь наибольшей длины. Его длина;
• визуализация орграфа. Вывод путей.

Количество вершин графа должно быть от 3 до 10 (если меньше 3-ех, то задача имеет тривиальное решение).
В соответствии с количеством введенных вершин должна появляться матрица соответствующей размерности, главная диагональ которой должна быть заполнена нулями (орграф не имеет петлей) без возможности изменения.
Ячейки, в которые не введены значения, должны считы-ваться как ячейки, заполненные нулями.
Все поля ввода должны «фильтровать» введенные дан-ные, т.е. выполнять проверку нажатия клавиш: в поля запрещено вводить какие-либо буквы, символы,которые неуместны в данном поле.
Во избежание сбоя, программа должна в определенные промежутки своей работы блокировать некоторые поля ввода, кнопки.
После вычисления путей (кратчайшего и наибольшего) программа должна по умолчанию построить матрицу смежности в графическом виде.
В случае, в котором путь существует, ПС должно давать возможность выбора вида визуализации (кратчайшего либо наибольшего).
При визуализации кратчайшего/наибольшего пути ПС должно выделять начальную и конечную вершины и выделять пути различным цветом.
Программа должна содержать соответствующую подсказку по работе с ней, а также выводить информацию об авторе.
Оглавление
ВВЕДЕНИЕ 3
1. ПОСТАНОВКА ЗАДАЧИ 5
2. ТРЕБОВАНИЯ К ПРОГРАММНОМУ СРЕДСТВУ 6
3. МЕТОД РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ 8
3.1 Основные понятия теории графов. 8
3.2 Алгоритм поиска в глубину 10
3.4 Алгоритм поиска кратчайшего пути 11
3.5 Поиск количества простых путей 12
4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ 13
4.1 Построение общей структуры программы 13
4.2 Выбор среды для реализации программного средства 13
4.3 Описание структур, типов данных и глобальных переменных 15
4.4 Описание основных подпрограмм 16
5. ТЕСТИРОВАНИЕ И ОТЛАДКА ПРОГРАММНОГО СРЕДСТВА 28
5.1 Тестирование и верификация программного средства 28
5.2 Показатели качества программного средства 30
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 34
ПРИЛОЖЕНИЕ 1. ТЕКСТ ПРОГРАММЫ 35
ПРИЛОЖЕНИЕ 2. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ 46
Список литературы
1. К. Берж, Теория графов и ее применения, Изд. иностр. лит, 1962.
2. В. А. Евстигнеев, Применение теории графов в про-граммировании, Наука, 1985.
3. В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич, Лекции по теории графов, Наука, 1990.
4. Н. Кристофидес, Теория графов, алгоритмический подход, Мир, 1978.
5. Фленов М. Е. Библия Delphi. — СПб.: БХВ-Петербург, 2004. — 880 с.
6. Культин Н. Б. Осноны программировании в Delphi 7. — СПб.: БХВ-Петербург. 2003. 608 с
7. В.В. Липаев. Тестирование программ. - М.: Радио и связь, 1986. - с. 147.
Похожие работы
Другие работы автора
Темы форума
Показать ещё
Интересное в блоге
Показать ещё
Прямой эфир