Алгоритм поиска источника орграфа

Алгоритм поиска источника орграфа

Министерство образования и науки

Республики Казахстан

Усть-Каменогорский колледж экономики и финансов

Специальность «Программное обеспечение вычислительной техники и автоматизированных систем»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по предмету: «Основы алгоритмизации и программирования»

Студент Ахмедова П.О

Группа ТП-31

Руководитель Хомова Т.М

Усть-Каменогорск

Задание на курсовое проектирование

«Источником» орграфа называют вершину, от которой достижимы все другие вершины. Разработать алгоритм и написать программу, позволяющую найти все источники орграфа.

.11.10

График выполнения курсового проекта

Содержание

Введение

1.  Основные элементы языка программирования

1.1       Обзор элементов языка программирования

2.  Описание решение задач проекта

2.1       Общая постановка задачи

2.2     Описание программного комплекса

.3       Макро блок-схема

.4       Таблица идентификаторов комплекса

2.4.1 Таблица глобального контекста

.4.2 Таблица локального контекста

.5         Описание наборов данных

2.6     Постановка проблемных подпрограмм

3.  Организация производства

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

3.2     Инструкция пользователю по работе программой

4.  ЗАКЛЮЧЕНИЕ

5.       Приложение А(текст программы)

.        Приложение В(окна результатов)

.        Список используемых источников

ВВЕДЕНИЕ

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

Карта дорог между городами может быть изображена в виде графа - набора вершин, обозначающих дороги.

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

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

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

. Тему дискретной математики - “Графы”:

Узнать: что такое орграф;

Что называется источником орграфа.

1. Основные элементы языка программирования

.1 Обзор элементов языка программирования

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

Рекурсия

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

Преимущество: достаточно сложные алгоритмы могут быть представлены в простой логической форме.

Недостатки:

рекурсивная форма организация алгоритма работает медленно.

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

Для представления орграфа используется двумерный массив

Массив

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

Для сохранения вершин пути и для определения источника орграфа используются множества

Множества.

Множество - это набор взаимосвязанных объектов, которые можно рассматривать как единое целое. Каждый такой объект, называемый элементом множества, должен принадлежать одному из простых типов, кроме вещественного типа.

2. Описание решение задач проекта

.1 Общая постановка задачи

Ориентированный граф (кратко орграф) - (мульти) граф, ребрам которого присвоено направление.

Направленные ребра именуются дугами.

Источник - вершина, от которой достижимы все остальные вершины.

Матрица смежности - это квадратная матрица, строки и столбцы которой соответствуют вершинам графа. Элемент матрицы (i,j) равен 1, если вершина i связана с вершиной j ребром, иначе элемент матрицы равен 0.

2.2 Описание программ комплекса

init - данная процедура создает матрицу смежности и заполняет её нулями.

Procedure init2 - данная процедура обнуляет массивы road (маршрут- номера точек карты) и incl (если точка с номером i включена в карту).

Procedure print - данная процедура выводит на экран матрицу смежности.Vvod - данная процедура заполняет массив единицами там, где заданно ребро орграфа.

Procedure step - данная процедура ищет в графе все возможные пути

Procedure findictok - данная процедура ищет источник орграфа который задан пользователем.

.3 Макро блок схема

Укрупненная схема приложения представлена на рис.1

Рис.1

2.4 Таблица идентификаторов комплекса

.4.1 Таблица глобального контекста

Таблица 1

2.4.2 Таблица локального контекста

Таблица 2

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<>j) then('m[',i,',',j,'] =>');(m[i,j]);;;;;

 step(s,f,p:byte);{s-точка, из которой делается шаг

f-конечная точка маршрута

p-номер искомой точки маршрута}

var

c:byte;                   {номер точки, в которую делается очередной шаг}

begin

if s=f then              {точки s и f совпали}

begin('Путь: ');i:=1 to p-1 do write(road[i],' ');;

for c:=1 to n do begin     {проверяем все вершины}

if (m[s,c]<>0) and (not incl[c]) then

{точка соединена с текущей и не включена в маршрут}

begin

road[p]:=c;              {добавим вершину в путь}

incl[c]:=true;            {пометим вершину как включеную}

z:=z+[c];(c,f,p+1);[c]:=false;[p]:=0;;;;;

step2;,st2:string;i:=1 to n doj:=1 to n dom[i,j]<>0 then q:=q+[i,j];:=q-z;i in e then

begin(I,st2);{заносим в переменную st2 значение переменной i}

st:=’источником является вершина под номером ‘+st2;

end;;(st);;

v<>6 do

writeln(' выберите номер из пункта меню. ');

writeln(' 1.создание новой матрицы ');

writeln(' 2.вывод матрицы на экран ');

writeln(' 3.создание ребр ');

writeln(' 4.нахождение всех путей');

writeln(' 5.нахождение источников');

read(v);

case v of

:init(m);

:print(m);

:vvod(m);

:beginstart:=1 to n dofinish:=1 to n dostart<>finish then(m);[1]:=start;[i]:=true;(start,finish,2);;;;

:step2;;;

Приложение В

Рис.8

Рис.9

Рис.10

Рис.11

Рис.12

Рис.13

Рис.14

Рис.15

Список используемых источников

1.       Культин «Турбо Паскаль 7.0»

2.       Новиков «Дискретная математика для программистов»

3.       Киракозов А.. «Поиск гамильтонова цикла». <http://rain.ifmo.ru/cat/view.php/vis/graph-circuits-cuts/hamiltonian-2005>

.        Берж К. «Теория графов и ее применения»

.        Немлюгин С.А. Turbo Pascal: практикум. - СПб.: Питер, 2002.

6.       Программирование на языке Паскаль: задачник / под ред. Усковой О.Ф. - СПб.: Питер, 2003.