Алгоритм поиска источника орграфа
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
it - данная процедура создает матрицу смежности и заполняет её нулями.
Procedure init2 - данная процедура обнуляет массивы road (маршрут- номера точек карты) и incl (если точка с номером i включена в карту).
Procedure print - данная процедура выводит на экран матрицу смежности.Vvod - данная процедура заполняет массив единицами там, где заданно ребро орграфа.
Procedure step - данная процедура ищет в графе все возможные пути
Procedure findictok - данная процедура ищет источник орграфа который задан пользователем.
.3 Макро блок схема
Укрупненная схема приложения представлена на рис.1
Рис.1
2.4 Таблица идентификаторов комплекса
.4.1 Таблица глобального контекста
Таблица 1
ИмяТипРазмерНазначение в программеnInteger-32768..32767Содержит количество реберqmn0..255Множество. Содержит номера вершин орграфаzmn0..255Множество. Содержит пройденный путьfInteger-32768..32767Конечная точка маршрутаpInteger-32768..32767Номер искомой точки маршрутаsInteger-32768..32767Точка, из которой делается шагmmyarray-32768..32767Массив, содержит матрицу смежностиroadinteger-32768..32767Массив, содержит номера точек картыinclbooleanTrue, falseIncl[i]:=true, если точка с номером I включена в roadеmn0..255Множество. Содержит номер источника орграфаninteger-32768..32767Кол-во вершин орграфа
2.4.2 Таблица локального контекста
Таблица 2
ИмяТипРазмерНазначение в программеiInteger-32768..32767Вспомогательная переменная для циклаjInteger-32768..32767Вспомогательная переменная для циклаststring0..255Вспомогательная переменнаяSt2string0..255Переменная для преобразования целого числа в строкуcbyte0..255Вспомогательная переменная цикла
2.5 Описание наборов данных
=array[1..n,1..n] of integer в этой матрице содержатся 1 и 0 то есть матрица соединение между вершинами (матрица смежности).:array[1..n] of integer в этой матрице содержится карта(вершины).:array[1..n] of boolean; проверяется точка I, включена ли она в карту.
2.6 Постановка проблемной под программы процедуры
step - данная процедура находит все возможные пути.
Блок схема процедуры step представлена на рис.2
Рис.2
init - данная процедура создает матрицу смежности и заполняет её нулями.
Блок схема процедуры init представлена на рис.3
Рис.3
init2 - данная процедура обнуляет массив road и incl.
Блок схема процедуры init2 представлена на рис.4
Рис.4print - данная процедура выводит на экран матрицу смежности.
Блок схема процедуры init2 представлена на рис.5
Рис.5
Vvod - данная процедура записывает введенный пользователем граф в файл.
Блок схема процедуры init2 представлена на рис.6
Рис.6
procedure findictok - данная процедура ищет источник орграфа который задан пользователем.
Блок схема процедуры init2 представлена на рис.7
Рис.7
программа орграф таблица язык
3. Организация производства
.1 Комплекс технических средств необходимых для решения задачи
Для обеспечения продуктивной работы приложению необходимо
Pentium I 200 Mhz
Mb Оперативной памяти
Интегрированная видео карата.
Windows 95, 98, XP, Vista, 7.
Клавиатура
Мышь
3.2 Инструкция пользователю по работе программой
При запуске программы появляется меню:
см. приложение В рис.8
Создание новой матрицы
заполняет матрицу смежности 0
вывод матрицы на экран
вывод графа в виде матрицы смежности
создание ребер
если заданные точки соединены между собой тогда нужно ввести 1, если нет то 0
нахождение всех путей
вывод на экран всех возможных путей в орграфе
нахождение источников
вывод на экран номер точки, от которой достижимы все вершины.
ЗАКЛЮЧЕНИЕ
Выполненная мной работа по нахождению источника орграфа позволяет найти точку в орграфе, от которой можно попасть во все остальные вершины.
Во время разработки данного приложения мною самостоятельно была изучена тема графы.
Теория графов применяется при анализе функционирования сложных систем, таких сети железных дорог, телефонные или компьютерные сети, ирригационные системы. эта теория традиционно является эффективным аппаратом формализации задач экономической и планово - производственной практики, применяется в автоматизации управления производством, в календарном и сетевом планировании.
Приложение A
wincrt;myarray=array [1..20,1..20] of integer;=set of byte;,z,e:mn;:myarray;,j,i,f,s,p,c,n:integer;
:array[1..20] of integer;:array[1..20] of boolean;,finish:integer;
init(var m:myarray); {процедура инициализации матрицы смежности}
writeln('введите кол-во вершин орграфа');
readln(n);i:=1 to n doj:=1 to n do[i,j]:=0;;
init2(var m:myarray); {процедура обнуления массивов}i:=1 to n do[i]:=0;[i]:=false;;
print(m:myarray);{процедура печати матрицы смежности}i:=1 to n do;j:=1 to n do(m[i,j]:2);;;;
vvod(var m:myarray);{процедура создание ребер}
writeln('Введите элементы матрицы смежности орграфа:');
readln;i:=1 to n doj:=1 to n do(i');(m[i,j]);;;;;
step(s,f,p:byte);{s-точка, из которой делается шаг
f-конечная точка маршрута
p-номер искомой точки маршрута}
var
c:byte;{номер точки, в которую делается очередной шаг}
begin
if s=f then{точки s и f совпали