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

Министерство образования и науки Республики Казахстан Усть-Каменогорский колледж экономики и финансов Специальность «Программное обеспечение вычислительной техники и автоматизированных систем».

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по предмету: «Основы алгоритмизации и программирования».

Студент Ахмедова П. О Группа ТП-31.

Руководитель Хомова Т. М Усть-Каменогорск.

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

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

11.11.10.

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

Содержание Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.

ЗАКЛЮЧЕНИЕ

.

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

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

7.

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

.

ВВЕДЕНИЕ

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

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

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

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

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

1. Тему дискретной математики — «Графы»:

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

— Как его можно представить в программе;

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

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

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

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

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

Недостатки:

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

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

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

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

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

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

2.1 Общая постановка задачи Ориентированный граф (кратко орграф) — (мульти) граф, ребрам которого присвоено направление.

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

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

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

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

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

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

Procedure print — данная процедура выводит на экран матрицу смежности.

Procedure Vvod — данная процедура заполняет массив единицами там, где заданно ребро орграфа.

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

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

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

Рис. 1.

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

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

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

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

m=array[1.n, 1. n] of integer в этой матрице содержатся 1 и 0 то есть матрица соединение между вершинами (матрица смежности).

road:array[1.n] of integer в этой матрице содержится карта (вершины).

incl:array[1.n] of boolean; проверяется точка I, включена ли она в карту.

2.6 Постановка проблемной под программы процедуры.

procedure step — данная процедура находит все возможные пути.

Блок схема процедуры step представлена на рис. 2.

Рис. 2.

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

Блок схема процедуры init представлена на рис. 3.

Рис. 3.

procedure init2 — данная процедура обнуляет массив road и incl.

Блок схема процедуры init2 представлена на рис. 4.

Рис. 4.

procedure print — данная процедура выводит на экран матрицу смежности.

Блок схема процедуры init2 представлена на рис. 5.

Рис. 5.

procedure Vvod — данная процедура записывает введенный пользователем граф в файл.

Блок схема процедуры init2 представлена на рис. 6.

Рис. 6.

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

Блок схема процедуры init2 представлена на рис. 7.

Рис. 7.

программа орграф таблица язык.

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

3.1 Комплекс технических средств необходимых для решения задачи Для обеспечения продуктивной работы приложению необходимо.

Pentium I 200 Mhz.

32 Mb Оперативной памяти Интегрированная видео карата.

Windows 95, 98, XP, Vista, 7.

Клавиатура Мышь.

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

см. приложение В рис. 8.

1 Создание новой матрицы.

— заполняет матрицу смежности 0.

2 вывод матрицы на экран.

— вывод графа в виде матрицы смежности.

3 создание ребер

— если заданные точки соединены между собой тогда нужно ввести 1, если нет то 0.

4 нахождение всех путей.

— вывод на экран всех возможных путей в орграфе.

5 нахождение источников.

— вывод на экран номер точки, от которой достижимы все вершины.

ЗАКЛЮЧЕНИЕ

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

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

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

Приложение A.

uses wincrt;

type myarray=array [1.20,1.20] of integer;

mn=set of byte;

var.

q, z, e:mn;

m:myarray;

v, j, i, f, s, p, c, n: integer;

road:array[1.20] of integer;

incl:array[1.20] of boolean;

start, finish: integer;

procedure init (var m: myarray); {процедура инициализации матрицы смежности}.

begin.

writeln ('введите кол-во вершин орграфа');

readln (n);

for i:=1 to n do.

for j:=1 to n do.

m[i, j]: =0;

end;

procedure init2(var m: myarray); {процедура обнуления массивов}.

begin.

for i:=1 to n do.

road[i]: =0;

incl[i]:=false;

end;

procedure print (m:myarray);{процедура печати матрицы смежности}.

begin.

for i:=1 to n do.

begin.

writeln;

for j:=1 to n do.

write (m[i, j]: 2);

end;

writeln;

end;

procedure vvod (var m: myarray);{процедура создание ребер}.

begin.

writeln ('Введите элементы матрицы смежности орграфа:');

readln;

for i:=1 to n do.

for j:=1 to n do.

begin.

if (i<>j) then.

begin.

write ('m[', i,',', j,'] =>');

read (m[i, j]);

readln;

end;

end;

end;

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

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

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

var.

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

begin.

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

begin.

write ('Путь: ');

for i:=1 to p-1 do write (road[i],' ');

writeln;

end.

else begin {выбираем очередную точку}.

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];

step (c, f, p+1);

incl[c]:=false;

road[p]:=0;

end;

end;

end;

end;

procedure step2;

var.

st, st2: string;

begin.

for i:=1 to n do.

for j:=1 to n do.

begin.

if m[i, j]<>0 then q:=q+[i, j];

e:=q-z;

if i in e then.

begin.

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

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

end;

end;

writeln (st);

end;

begin.

while v<>6 do.

begin.

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

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

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

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

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

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

read (v);

case v of.

1:init (m);

2:print (m);

3:vvod (m);

4:begin.

for start:=1 to n do.

for finish:=1 to n do.

begin.

if start<>finish then.

begin.

init2(m);

road[1]: =start;

incl[i]:=true;

step (start, finish, 2);

end;

end;

end;

5:step2;

end;

end;

Приложение В Рис. 8.

Рис. 9.

Рис. 10.

Рис. 11.

Рис. 12.

Рис. 13.

Рис. 14.

Рис. 15.

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

.

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

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

3. Киракозов А. «Поиск гамильтонова цикла».

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

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

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