Ребят я без понятия. Задача звучит именно так. Стало быть остальные условия можно задавать самому, исходя из простоты алгоритма... Мне именно алгоритм нужен ;-)
Алгоритм обхода графа (поиска) в ширину
Паскаль:
procedure breadthsearch(v:integer);
var q:ARRAY[1..100] of 0..100;
x,j,l,r:integer;
begin
fillchar(q,sizeof(q),0);
l:=0;
r:=0;
inc(r);
q[r]:=v;
mark[v]:=true;
while
l<r do begin
inc(l);
x:=q[l];
for j:=1 to n do
if (a[x,j]=1) and(not mark[j]) then
begin
inc(r); q[r]:=j;
mark[j]:=true;
d[j]:=d[x]+1;
end;
end;
end;
Явно не явно, но тем не менее - есть конкретная задача :-) Перерыл уже все, даже большой математический справочник, и все равно не могу понять, как это кол-во ребер сосчитать :-) Тем более, что граф ориентированный :-(
Normal, ответ должен быть в условии.
В случае задания графа в виде списка ребер нужно определить размер списка.
В случае матрицы связности - посчитать в ней количество единичек (в случае ориентированного графа без петлей)
Ален - цитирую : "Методические указания и варианты индивидуальных заданий к лабораторным работам" (Е-бург 2004) Лаб. работа N5 Вариант 4. Сосчитать количество ребер заданного ориентированного графа. Вот и думай тут, что конкретно они
имелли в виду и как сие решать :-)
действительно задача очень сильно зависит от исходных данных, для каких-то представлений графа (например когда граф задн списком рёбер) решение может быть тривиальным (длина списка), но в общем случае наиболее подходящим ИМХО будет поиск в ширину с включением счётчика проходимы рёбер(естьстественно
конкретная реализацитя алгоритма зависит от формата представления графа :-) )
кстати нужна конкретная прога или просто описание алгоритма на каком-то формально языке с оперированием понятий "вершина" и "ребро"?
реализация проги на Паскале будет зависеть от формата входных данных. т.е. способа представления графа - если он в условиях задачи не определён, то надо взять какой-нибудть стандартный (например матрица связности) и написать для него
сам алгоритм есть в любой книге по дискретным алгоритмам на
графах - грубо говоря начиная с какой-то вершины пишем в очередь все вершины смежные с ней, затем из очереди берём очередную вершину и пишем в очередь все смежные с ней, которые ещё в очередь не попадали - при обработке очередной вершин писать в счётчик кол-во исходящих для неё рёбер
удачи ;-)
PS. Не надо поиска в ширину. Граф невозможно задать, не указав его ребра
твержу это второй день человеку!
Цитата: От пользователя: Normal
Сосчитать количество ребер заданного ориентированного
графа.
Пфигу какой граф, ориентированный или нет, на количество ребер это не влияет никак!
Граф задан. Покажите, где?
Вот примеры, задач для графов:
Дискретная математика
№ 756AF531 delphi
алгоритм на графах
Написать
алгоритм поиска в ширину для графа, заданного:
а)матрицей смежности
б)массивом смежности
№ 756AF532 pascal
Решение задачи комивояжера методом Литтла, решение оптимизации матрицы 5*5.
№ 756AF533 delphi
Построить граф G*=(E*,G*) путём добавления начального графа
G=(V,E) с помощью сумирования новых вершин и дуг GX8={X6}
№ 756AF534 delphi
Программа для одновременного отыскания собственных значений и собственных векторов в симметрической матрице методом итерации
№ 756AF535 c c++
Найти диаметр графа, т.е. максимум расстояний между
всевозможными парами его вершин. Программу написать с использованием вызова функций и подпрограмм. Использование глобальных переменных запрещено.
№ 756AF536 c c++
Задана система двусторонних дорог найти замкнутый путь длинной не больше n (n задано) проходя через каждую дорогу не белее 1
раз
№ 756AF537 c
Разработать программу, осуществляющую нахождение кратчайшего пути с помощью алгоритма Дейкстра
В данной работе: 7 рисунков, 1 программа, 1 приложение, 35 листов.
Ключевые слова: граф, алгоритм, поиск,
ширина, программа, аргумент,
элемент, массив, очередь, память, время, сравнение.
Цель работы: Исследовать эффективность алгоритма поиска в графе в
ширину.
Результат работы программы: количество сравнений элемента с ключом
поиска и время, за
которое был найден элемент по данному алгоритму поиска.
Областью применение данного алгоритма может быть разнообразна, на
пример при построении карт местности: вершины графа – города, связи –
дороги.
Содержание
Введение…………………………………………………………………..5
стр.
1. Краткая теория………………………………………………………..6 стр.
2. Анализ алгоритма……………………………………………………11 стр.
3. Спецификация задачи……………………………………………….14 стр.
3.1 Входные и выходные данные…………………………………14 стр.
3.2 Используемые
процедуры…………………………………….14 стр.
4. Программа на языке Turbo Pascal..…………………………………15 стр.
4.1 Листинг программы…………..………….……………………15 стр.
4.2 Контрольный пример для тестирования №1….……………..26 стр.
4.3 Контрольный пример для тестирования
№2….……………..26 стр.
4.4 Руководство пользователя…………………………………….27 стр.
5. Результаты тестирования……………………………………………28 стр.
Заключение………………………………………………………………33 стр.
Список используемой литературы……………………………………..34 стр.
Приложение
А…………………………………………………………….35 стр.
Введение.
Графы встречаются в сотнях разных задач, и
алгоритмы обработки графов
очень важны.
Существует множество разработанных алгоритмов для решения различных
задач из самых разных областей человеческой деятельности. Формулировка
задачи описывает, каким требованиям должно удовлетворять решение задачи,
а
алгоритм, решающий эту задачу, находит объект, этим требованиям
удовлетворяющий. ([1])
В этой работе, мы не будем давать четкого определения алгоритма, а
попытаемся проанализировать и изучить алгоритм поиска в ширину в графе.
Поиском по
заданному аргументу называется алгоритм, определяющий
соответствие ключа с заданным аргументом. Алгоритм поиска в ширину может
быть использован для просмотра созданного графа, чтобы узнать состав
информационных вершин для последующего поиска.
В
результате работы алгоритма поиска заданная вершина может быть
найдена или может быть отмечено отсутствие ее в исходных данных.
Если заданная информационная вершина найдена, то происходит вывод об
успешном окончании поиска, вывод времени поиска и времени поиска
ключа.
Краткая теория.
Очевидно, что наиболее понятный и полезный для
человека способ
представления графа — изображение графа на плоскости в виде точек и
соединяющих их линий — будет совершенно бесполезным, если мы захотим решать
с помощью ЭВМ задачи, связанные с графами. Выбор соответствующей структуры
данных для
представления графов имеет принципиальное влияние на
эффективность алгоритмов, поэтому мы подробнее остановимся на этой
проблеме. Мы покажем несколько различных способов представления и кратко
разберем их основные достоинства и недостатки.
Мы
будем рассматривать как ориентированные, так и неориентированные
графы. Граф мы будем всегда обозначать G = (V,E), где V обозначает
множество вершин, а Е — множество ребер, причем Е ( V X V для
ориентированного графа и Е({{х,у}: х,у ( V ? х(у} для
неориентированного
графа. Будем также использовать обозначения |V| = n и |Е| = m.
В теории графов классическим способом представления графа служит
матрица инциденций. Это матрица А с n строками, соответствующими вершинам,
и m столбцами, соответствующими
ребрам. Для ориентированного графа столбец,
соответствующий дуге ( E, содержит —1 в строке, соответствующей
вершине х, 1 в строке, соответствующей вершине у, и нули во всех остальных
строках (петлю, т. е. дугу вида , удобно представлять иным значением
в строке
х, например, 2). В случае неориентированного графа столбец,
соответствующий ребру {х,у}, содержит 1 в строках, соответствующих х и у, и
нули в остальных строках. Это проиллюстрировано на рис. 2.1. С
алгоритмической точки зрения матрица инциденций
является, вероятно, самым
худшим способом представления графа, который только можно себе представить.
Во-первых, он требует nm ячеек памяти, причем большинство этих ячеек вообще
занято нулями. Неудобен также доступ к информации. Ответ на элементарные
вопросы типа
«существует ли дуга ?», «к каким вершинам ведут ребра из
х?» требует в худшем случае перебора всех столбцов матрицы, а
следовательно, m шагов.
Лучшим способом представления графа является матрица смежности,
определяемая как матрица В = [b•j]
размера nхm,
|<|<|<|<|<|<|<|
|1|1|3|3|5|5|6|
|,|,|,|,|,|,|,|
|2|3|2|4|4|6|5|
|>|>|>|>|>|>|>|
Рис. 1. а) Ориентированный граф и его матрица инциденций;
б) Неориентированный граф и его матрица инциденций.
где bij = 1, если существует ребро, идущее из вершины х в вершину у, и bij
= 0 в противном случае. Здесь мы
подразумеваем, что ребро {х, у}
неориентированного графа идет как от х к у, так и от у к х, так что матрица
смежности такого графа всегда является симметричной. Это проиллюстрировано
на рис. 2.
Основным преимуществом матрицы смежности является тот факт, что за
один
шаг можно получить ответ на вопрос «существует ли ребро из х в y?».
Недостатком же является тот факт, что независимо от числа ребер объем
занятой памяти составляет n2. На практике это неудобство можно иногда
уменьшить, храня целую строку
(столбец) матрицы в одном машинном слове —
это возможно для малых n.
В качестве еще одного аргумента против использования матрицы смежности
приведем теорему о числе шагов, которое
должен выполнить алгоритм, проверяющий на основе матрицы смежности
некоторое свойство графа.
Пусть Р — некоторое свойство графа P(G) = 0 или P(G)=1 в зависимости от
того, обладает или не обладает G нашим свойством. Предположим, что свойство
Р удовлетворяет следующим трем условиям:
(а) P(G)=P(G'), если графы G и G'
изоморфны;
(б) P(G) = 0 для произвольного пустого графа и P(G)=1 для
произвольного полного графа с достаточно большим числом вершин;
1 2 3 4 5 6 1 2 3 4 5 6
1 0 1 1 0 0 0 1 0 1 1 0 1 0
2 0 0 0 0 0 0 2 1 0 1 0 1 0
3 0 1 0 1 0 0 3 1 1 0 1 0 0
4 0 0 0 0 0 0 4 0 0 1 0 1 1
5 0 0 0 1 0 1 5 1 1 0 1 0 1
6 0
0 0 0 1 0 6 0 0 0 1 1 0
Рис. 2. Матрицы инциденций для графов на рис.1.
(в) добавление ребра не нарушает свойства Р, т. е. P(G), G’ =
< V, Е> U >, v C V.
Более экономным в отношении
памяти (особенно в случае, неплотных
графов, когда m гораздо меньше n2) является метод представления графа с
помощью списка пар, соответствующих его ребрам. Пара соответствует
дуге <х, у>, если граф ориентированный, и ребру {х, y} в случае
неориентированного графа(рис. 3). Очевидно, что объем памяти в этом случае
составляет 2т. Неудобством является большое число шагов — порядка т в
худшем случае, — необходимое для получения множества вершин, к которым
ведут ребра из данной вершины.
Ситуацию можно значительно улучшить, упорядочив множество пар
лексикографически и применяя двоичный поиск, но лучшим решением во многих
случаях оказывается структура
Рис.3. Списки ребер соответствующие графам на рис.1.
данных, которую мы будем называть списками инцидентности.
Она содержит для
каждой вершины v C V список вершин и, таких что v -> u (или v — ив случае
неориентированного графа). Точнее, каждый элемент такого списка является
записью г, содержащей вершину г. строка и указатель г. след на следующую
запись в списке (г.
след = nil для последней записи в списке). Начало
каждого списка хранится в таблице НАЧАЛО; точнее, HAЧАЛО[v] является
указателем на начало списка, содержащего вершины из множества {u: v+u} ({u:
v - u} для неориентированного графа). Весь такой список обычно
неформально
будем обозначать 3AПИСЬ[v], а цикл, выполняющий определенную операцию для
каждого элемента и из этого списка в произвольной, но четко установленной
последовательности, соответствующей очередности элементов в списке, будем
записывать «for u C ЗАПИСЬ
[v] do ...».
Отметим, что для неориентированных графов каждое ребро {u, v}
представлено дважды: через вершину v в списке ЗАПИСЬ[u] и через вершину и в
списке ЗАПИСЬ[v]. Во многих алгоритмах структура графа динамически
модифицируется добавлением и
удалением ребер. В таких случаях полагаем, что
в наших списках инцидентности элемент списка ЗАПИСЬ [u], содержащий вершину
и, снабжен указателем на элемент списка 3AПИCЬ[v], содержащий вершину и, и
что каждый элемент списка содержит указатель не только к следующему
элементу, но и к предыдущему. Тогда удаляя некоторый элемент
[pic]
Рис.4. Списки инцидентности ЗПИСЬ[v], v =V, соответствующие графам на
рис.1.
из списка, мы можем легко за число шагов, ограниченное константой,
удалить
другой элемент, представляющий то же самое ребро, не просматривая список,
содержащий этот элемент.
Аналогичным способом определяем для каждой вершины и неориентированного
графа список ПРЕДШ[v], содержащий вершины из множества (u: u -> v).
Число ячеек памяти, необходимое для представления графа с помощью
списков инцидентности, будет, очевидно, иметь порядок m + n. На рис.4
представлены списки инцидентности, соответствующие графам на рис. 1.
2. Анализ
алгоритма.
Рассмотрим метод поиска в графе, называемый поиском в ширину (англ:
breadth first search). Прежде чем описать его, отметим, что при поиске в
глубину чем позднее будет посещена вершина, тем раньше она будет
использована — точнее,
так будет при допущении, что вторая вершина
посещается перед использованием первой. Это прямое следствие того факта,
что просмотренные, но еще не использованные вершины скапливаются в стеке.
Поиск в ширину, грубо говоря, основывается на замене стека очередью.
После
такой модификации, чем раньше посещается вершина (помещается в очередь),
тем раньше она используется (удаляется из очереди). Использование вершины
происходит с помощью просмотра сразу всех еще не просмотренных соседей этой
вершины. Вся процедура поиска
представлена ниже (данная процедура
используется также и для просмотра графа, и в псевдокоде, описанном ниже,
отсутствуют операторы, которые не используются для поиска).
1 procedure WS (v);
(*поиск в ширину в графе с началом в вершине v;
переменные НОВЫЙ, ЗАПИСЬ — глобальные *)
2 begin
3 ОЧЕРЕДЬ := ?; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь
4 while ОЧЕРЕДЬ ? ? do
5 begin р<= ОЧЕРЕДЬ; посетить р;
6 for u ? ЗАПИСЬ [р] do
7 if
НОВЫЙ [u] then
8 begin ОЧЕРЕДЬ <= u; НОВЫЙ [u]:=ложь
9 end
10 end
11. end
Примечание: в 7-й строке псевдокода кроме условия НОВЫЙ[u] должно также
выполниться условие наличия связи (ребра) между v-й
и u-й вершинами. Для
установки наличия ребра сначала в списке v-й вершины ищется информационное
значение и-й вершины. Если оно найдено, то ребро установлено, если нет, то
информационное значение v-й вершины ищется в списке и-й вершины, т.е.
наоборот. В результате
добавления двух лишних циклов поиска общий алгоритм
поиска несколько теряет компактность, но на быстродействии в целом это не
сказывается.
1 procedure Write_S;
2 begin
3 for v ? V do НОВЫЙ[u]:= истина; (* инициализация *)
4
for v ? V do
5 if HOBЫЙ[v] then WG(v)
6 end
Способом, аналогичным тому, какой был применен для поиска в глубину,
можно легко показать, что вызов процедуры WS(v) приводит к посещению всех
вершин связной компоненты графа, содержащей
вершину v, причем каждая
вершина просматривается в точности один раз. Вычислительная сложность
поиска в ширину также имеет порядок О(m + n), так как каждая вершина
помещается в очередь и удаляется из очереди в точности один раз, а число
итераций цикла
6, очевидно, будет иметь порядок числа ребер графа.
В очереди помещены сначала вершины, находящиеся на расстоянии 0 от v
(т. е. сама вершина v), затем поочередно все новые вершины, достижимые из
v, т. е. вершины, находящиеся на расстоянии 1 от v, и т. д. Под
расстоянием
здесь мы понимаем длину кратчайшего пути. Предположим теперь, что мы уже
рассмотрели все вершины, находящиеся на расстоянии, не превосходящем r, от
v, что очередь содержит все вершины, находящиеся от v на расстоянии r, и
только эти вершины.
Использовав каждую вершину р, находящуюся в очереди,
наша процедура просматривает некоторые новые вершины, и каждая такая новая
вершина u находится, очевидно, на расстоянии г + 1 от v. После
использования всех вершин из очереди, находящихся на расстоянии r от
v, она
(очередь), очевидно, содержит множество вершин, находящихся на расстоянии r
+ 1 от v, и легко заметить, что условие индукции выполняется и для
расстояния r + 1.
На рис. 5 представлен граф, вершины которого занумерованы согласно
очередности, в которой они посещаются в процессе поиска в глубину.
Как и в случае поиска в глубину, процедуру WS можно использовать без
всяких модификаций и тогда, когда списки
Рис. 5 Нумерация вершин графа (в
скобках), соответствующая
очередности, в которой они просматриваются в процессе поиска в ширину.
инцидентности ЗАПИСЬ[v], v = V, определяют некоторый ориентированный граф.
Очевидно, что тогда посещаются только те вершины, до которых существует
путь от вершины,
с которой мы начинаем поиск
3. Спецификация задачи
3.1 Входные и выходные данные
ver – массив вершин графа, заполняемый случайным образом целыми числами в
диапазоне от 0 до 1000;
nv -
массив флагов проверки вершин;
ocher – массив для организации очереди, заполняемой значениями
рассматриваемых информационных вершин графа;
raz – переменная целочисленного типа, определяющая в программе размер
создаваемого графа;
schet –
счетчик количества сравнений в процедуре поиска;
key – вводимый с клавиатуры ключ поиска;
mgsi – переменная логического типа, разрешающая вывод списка инцидентности
графа;
prosm - переменная логического типа, превращающая процедуру поиска WS в
процедуру просмотра графа;
find - переменная логического типа, определяемая при нахождении искомой
информационной вершины;
craz, menu, mg, sormen – переменные символьного типа для работы с меню
программы.
3.2
Используемые процедуры
Make_Graph – процедура создания графа в динамической памяти;
WS - процедура просмотра графа с v-той вершины методом поиска в ширину;
Write_S – процедура инициализации признаков просмотра вершин и управляющая
процедурой WS;
Sort -
процедура сортировки вершин графа по неубыванию.
4. Текст программы на языке TURBO PASCAL
4.1 Листинг программы.
{$S+} {$R+} {$I+} {$M 65520,0,655360}
program graph;
uses crt,newtimer;
const
maxraz=400;
type index=^list;
list= record
inf: word;
next: index;
end;
connection=array[1..maxraz] of index;
var
el,em,size: pointer;
lst,m: connection;
ver: array[1..maxraz] of word; {массив вершин}
Nw: array[1..maxraz] of boolean;
ocher: array[1..maxraz+1] of integer;
raz: integer;
exch,fil,i,j,l,schet,v,u,p: word;
key,kols,t,tm: longint;
mgsi,mem,sor,prosm,find: boolean;
craz,menu,mg,sormen:char;
{------------------------------------------------------
***Процедура создания графа в динамической памяти***}
procedure Make_Graph(mgsi: boolean);
label Er;
var
n: index;
i,j: word;
kolvo: longint;
spro: boolean;
begin
randomize;
for i:=1 to raz do begin
ver[i]:=random(1000);
end;
kolvo:=0;
for i:=1 to raz do begin
lst[i]:=nil;
for j:=1 to raz do begin
spro:=true;
if
j=raz then goto Er;
if j=i then inc(j);
n:=nil;
n:=lst[j];
if lst[j]<>nil then
repeat
if n^.inf=ver[i] then spro:=false;
n:=n^.next;
until (n=nil)
or (not(spro));
if (round(random)=1) and spro then
begin
new(m[i]);
inc(kolvo);
m[i]^.inf:=ver[j];
m[i]^.next:=lst[i];
lst[i]:=m[i];
end;
Er:
end;
end;
writeln;
if mgsi then {ВЫВОД СВЯЗЕЙ ВЕРШИН}
for i:=1 to raz do {}
begin {}
write(ver[i],'-'); {}
m[i]:=lst[i]; {}
if m[i]<>nil then {}
repeat {}
write(m[i]^.inf,'-'); {}
m[i]:=m[i]^.next;
{}
until m[i]=nil; {}
writeln(''); writeln; {}
end; {}
writeln('КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: ',kolvo);
end;
{------------------------------------------------------
***Процедура просмотра графа с v-той вершины методом поиска в ширину***}
Procedure WS(v:word; var find: boolean;
var schet: word);
var {v - пор. номер вершины графа}
ik,oo,o9,o3,op: integer;
rebro: boolean;
begin {оо - размер очереди в данном цикле}
ocher[1]:=v; oo:=1; {вставка текущего индекса вершины в начало очереди}
Nw[v]:=False; {флаг на вершину текущего индекса}
while oo>0 do begin {пока есть
очередь...}
p:=ocher[1];{удаление 1-го элемента из очереди и присваивание его p}
for op:=1 to oo-1 do ocher[op]:=ocher[op+1]; ocher[oo]:=0;
dec(oo);
inc(schet); {счетчик сравнений}
if not(prosm) and (ver[p]=key) then {if ver[p]=key...}
begin
find:=true;
exit; {поиск окончен}
end;
{вывод (просмотр) информации вершины}
if prosm then begin
if wherex>=79 then writeln;
write(ver[p],' ');
end;
o9:=oo;
for u:=1 to o9 do {u изменяется в диапазоне размера очереди}
begin
rebro:=false;{связи между ver[v] и ver[u] нет}
{указатель на начало списка связей v-й вершины}
m[v]:=lst[v];
while m[v]<>nil do
begin {поиск значения ver[u] в списке связей v-й вершины}
if m[v]^.inf=ver[u] then begin
{ребро есть} rebro:=true;
break;
end;
m[v]:=m[v]^.next; {ребра пока нет...}
end;
{если связь не установлена, поищем связь с ver[v] в списке u-й вершины,
т.е. наоборот...}
if not(rebro) then
begin
m[u]:=lst[u];{указатель на начало списка связей u-й
вершины}
while m[u]<>nil do
begin
if m[u]^.inf=ver[v] then begin
rebro:=true;
break;
end;
m[u]:=m[u]^.next;
end;
end;
{если связь все таки есть и u-я вершина еще не рассмотрена...}
if rebro and Nw[u] then
begin
inc(oo); {вставка u в начало очереди}
for
op:=oo downto 2 do ocher[op]:=ocher[op-1];
ocher[1]:=u;
Nw[u]:=False;{флаг на вершину с индексом u}
end;
end;
end;
end;
{------------------------------------------------------
***Процедура просмотра
графа***}
Procedure Write_S(key: longint; prosm: boolean;
var find: boolean; var schet: word);
begin
{инициализация признаков просмотра вершин}
for i:=1 to raz do Nw[i]:=true;
for i:=1 to raz do
{если из raz вершин i-ая не
использована, то смотреть граф с i-ой
вершины}
if Nw[i] and not(find) then WS(i,find,schet);
end;
{------------------------------------------------------
***Процедура сортировки вершин по неубыванию***}
procedure Sort;
begin
for l:=1 to
raz-1 do
for j:=1 to raz-l do
if ver[j]>ver[j+1] then
begin
exch:=ver[j];
el:=lst[j];
em:=m[j];
ver[j]:=ver[j+1];
lst[j]:=lst[j+1];
m[j]:=m[j+1];
ver[j+1]:=exch;
lst[j+1]:=el;
m[j+1]:=em;
end;
end;
{=====================================================}
begin
while menu<>'4' do
begin
textmode(1);
textbackground(blue);
clrscr;
textcolor(red);
gotoxy(16,3); writeln('Г Р А Ф Ы');
textcolor(white);gotoxy(5,5);
writeln('* Исследование поиска в ширину *');
textcolor(black); gotoxy(7,22);
writeln('Created by Andrew Spikhailo');
gotoxy(15,24); write('ARMAVIR 2001');
textcolor(white);
gotoxy(7,10); write('+-----------MENU-----------?');
gotoxy(7,11); write('|');textcolor(green);
write('1 Создание графа ');
textcolor(white);write('|');
gotoxy(7,12); write('|');textcolor(green);
write('2 Просмотр графа ');
textcolor(white);write('|');
gotoxy(7,13); write('|');textcolor(green);
write('3 Поиск элемента графа ');
textcolor(white);write('|');
gotoxy(7,14); write('|');textcolor(green);
write('4 Выход ');
textcolor(white);write('|');
gotoxy(7,15); write('|');textcolor(white+128);
write('Выберите номер пункта меню');
textcolor(white);write('|');
gotoxy(7,16); write('?--------------------------+');
menu:=readkey;
case menu of
'1': begin
{освобождение памяти, если она была занята}
textmode(2);
textbackground(blue);
clrscr; textcolor(lightgreen);
if mem then release(size);
repeat
clrscr;
write('Число вершин графа: ');
writeln('(1) -
десять');
gotoxy(21,wherey);
writeln('(2) - сто');
gotoxy(21,wherey);
writeln('(3) - четыреста');
gotoxy(21,wherey);
write('(4) -
другое...');
raz:=0;
repeat
craz:=readkey;
case craz of
'1': raz:=10;
'2': raz:=100;
'3': raz:=400;
'4': begin
write(' ___');
gotoxy(wherex-3,wherey);
read(raz);
if (raz<=0) or (raz>400) then begin
raz:=0;
gotoxy(38,wherey-1);
write('ERROR...');
delay(1000);
end;
end;
end;
until (craz='1') or (craz='2') or (craz='3') or (craz='4');
clrscr;
until raz>0;
writeln;
write('вывод списка инцидентности графа: ');
writeln('0 - запретить');
gotoxy(35,wherey);
write('1 - разрешить');
mg:=readkey;
if mg='1' then mgsi:=true
else
mgsi:=false;
clrscr;
mark(size);
Make_Graph(mgsi);
mem:=true;{теперь память можно освобождать}
sor:=false; {вершины не отсортированы}
readkey;
end;
'2': begin {Просмотр графа }
textmode(2);
textbackground(blue);
clrscr; textcolor(lightgreen);
gotoxy(32,3); Writeln('Просмотр графа:');
key:=-1;
find:=false;
prosm:=true; schet:=0;
Write_S(key,prosm,find,schet); writeln;
readkey;
end;
'3': begin {Поиск элемента графа}
clrscr; textcolor(lightgreen);
if not(sor) then begin
writeln('Отсортировать вершины по неубыванию?');
writeln(' 1-ДА');
writeln(' 2-НЕТ');
sormen:=readkey;
if sormen='1' then begin
Sort;
sor:=true;
end;
end;
prosm:=false;
write('Что будем искать : ');
readln(key); writeln;
start(t);
kols:=0;
for fil:=1 to 10000 do
begin
schet:=0;
find:=false;
Write_S(key,prosm,find,schet); {поиск в ширину}
kols:=kols+schet;
end;
stop(t);
if not(find) then write('К сожалению такой вершины нет...')
else begin
writeln('Вершина графа ',ver[p],' найдена!');
writeln('Количество сравнений:
',kols/10000:5:1);
report('Время поиска вершины',t);
end;
readkey;
end;
end;
end;
end.
4.2 Контрольный пример для тестирования №1.
Количество вершин графа – 5, ребра между ними формируются случайным
образом.
Список инцидентности созданного графа:
74 497-174-§
174 §
55 497-§
497 §
661 497-§
КОЛ-ВО РЕБЕР
СОЗДАННОГО ГРАФА: 4
Содержание информационных вершин: 74 174 55 497 661
Примечание: символ «§» соответствует концу списка (nil).
Полученный граф изображен на рис.6
55 74
497
661 174
рис. 6
4.3 Контрольный пример для тестирования №2.
Количество вершин графа – 7, ребра между
ними формируются случайным
образом.
Список инцидентности созданного графа:
704 66-373-434-§
434 373-§
766 706-373-434-§
373 66-§
66 §
706 66-704-§
454 706-66-373-§
КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: 13
Содержание информационных вершин: 704 434 766 373 66 706 454
Примечание: символ «§» соответствует концу списка (nil).
Полученный граф изображен на рис.7
704
454 66
373 434
706 766
рис. 7
4.4 Руководство пользователя.
При запуске программы на экране появляется основное меню программы,
которое состоит из четырех пунктов:
1 Создание графа
2 Просмотр графа
3 Поиск элемента графа
4 Выход.
Выбор интересующего пункта
осуществляется с помощью клавиш «1», «2», «3» и
«4».
а) «Создание графа»
Выбрав пункт «Создание графа», на экране появится меню выбора
количества вершин графа: 10, 100, 400 и другое.
Нажав клавишу с порядковым номером пункта меню,
Вы выберете
необходимое количество вершин. Далее, нажав клавишу 1 Вы разрешите
программе вывести на экран список инцидентности графа, а нажав 0 –
запретите.
б) «Просмотр графа»
При выборе пункта «Просмотр графа», на экране
появится список
информационных вершин созданного графа.
в) «Поиск элемента графа»
При выборе пункта «Поиск элемента графа» на экране сначала появляется
запрос на сортировку информационных вершин. Затем Вам предстоит задать
элемент поиска в
графе, после чего при удачном поиске на экран будет
выведено время поиска и среднее количество сравнений. Время поиска
вычисляется с помощью процедур Start,Stop и Report, описанных в модуле
Newtimer. Листинг модуля Newtimer описан в Приложении А.
г) «Выход»
При выборе пункта «Выход» программа прекращает свою работу.
5. Результаты тестирования
Исследуем результаты работы программы, для чего сначала измерим
время
поиска для трех графов из 100, 200 и 400 элементов, отсортированных в
порядке возрастания и не отсортированных и сравним полученные результаты.
Количество информационных вершин – 10, вершины не отсортированы, их
содержание:
97 920 635 286 590 938
981 716 427 474
Что будем искать : 427
Вершина графа 427 найдена!
Количество сравнений: 9.0
Момент запуска: 23:53:46.50
Момент остановки: 23:53:46.66
Время поиска вершины : 0.00001 cek.
Количество информационных вершин – 10, вершины
отсортированы, их
содержание:
32 192 234 243 297 324 775 804 982 986
Что будем искать : 192
Вершина графа 192 найдена!
Количество сравнений: 2.0
Момент запуска: 23:55:28.33
Момент остановки: 23:55:28.44
Время поиска вершины : 0.00001 cek.
Как показал эксперимент, сортировка информационных вершин графа влияет
на время поиска элемента методом
просмотра в ширину в графе. Уменьшается
количество сравнений, что также повышает быстродействие алгоритма. Однако
это существенно повышает эффективность алгоритма только при намного большем
количестве вершин, чем в произведенных опытах.
Время поиска даже при
максимально возможном количестве вершин (400)
настолько мало, что засечь его не представляется возможным. Поэтому процесс
поиска повторяется 10000 раз. Точное время вычисляется в подключенном
модуле Newtimer по формуле:
T=Q/n
,где
Q- общее время поиска;
n – количество циклов поиска (10000).
Полученное время практически не заметно, так как исследовались графы
небольшой размерности, но если графы будут размерности более чем 1 миллиард
вершин, то время будет ощутимо. И
можно получить выгоду из алгоритма поиска
в ширину, если использовать его сразу для максимального количества
элементов, а не несколько раз, но используя немного элементов.
Таким образом, алгоритм поиска в ширину в графе является достаточно
эффективным
и может использоваться в программах для быстрого поиска
элементов.
Заключение
Современное состояние и тенденции развития вычислительной техники как
основного инструмента информатики таковы, что наряду с увеличением
функциональности вычислительная техника приобретает свойства, позволяющие
работать на ней пользователю, не разбирающемуся в программировании. В этот
период появился более качественный интерфейс
программ. Появились структуры
графических данных и более крупные, интегральные информационные единицы –
объекты. Следствием стало бурное развитие объектно-ориентированных систем
программирования, таких как Visual C++, Visual BASIC и других, в основе
которых
лежит обработка объектных структур данных. Также появились новые
языки программирования ADA, OCCAM.([3]) И если раньше большой популярностью
пользовались простые линейные алгоритмы то в настоящее время алгоритмы
таких типов как деревья, графы, списки, очереди –
получают все большее
распространение.
Данный алгоритм может найти своё применение в программах для
транспортных и коммуникационных сетей, таких как: железнодорожной
транспортной сети, где вершины - станции, связи – дороги, таксомоторная
сеть: вершины – места стоянки автомобилей, связи – пути подъезда;
перемещение потока вещества по системе труб в определенный пункт назначения
и т.д. На основе алгоритма поиска в ширину в графе можно построить
программу вывода дерева наименьшей
стоимости, что позволит рассчитывать
кратчайшие пути к определенному месту назначения (вершине).
Таким образом, развитие информационных технологий, их проникновение во
все области жизнедеятельности человека требуют компьютерного отображения
информации в виде
соответствующих структур данных. И графы, являясь одной
из частей этих структур данных, играют важную роль в современном
программировании, графы встречаются в сотнях разных задач.
Список литературы:
1.
Вирт Н. Алгоритмы и структуры данных.– М.: Мир, 1989.
2. Кнут Д. Искусство программирования для ЭВМ. – В 7 т. - М.: Мир,
1876.
3. Лойко В.И. Структуры и алгоритмы данных ЭВМ: Курс лекций для спец.
220400 – Краснодар: КубГТУ, 1998.
4.
Марченко А.И., «Программирование в среде «Turbo Pascal 7.0»,
«Век+», Киев 1999 г.
Подпись_________________________Дата___________________________
Приложение А
Листинг модуля Newtimer
unit newtimer;
interface
procedure start(var x: longint); {определяет время начала работы}
procedure stop(var x: longint); {определяет время окончания работы}
procedure format(hour, min, sec, hund: word);
procedure
Report(Msg:string; x:longint);
implementation
uses dos;
var
hour_start, min_start, sec_start, hund_start,
hour_stop, min_stop, sec_stop, hund_stop,
hour, min, sec, hund: word;
systimer : longint absolute $0040 : $006c;
procedure start;
begin
gettime(hour_start, min_start, sec_start, hund_start);
x:=systimer;
while x=systimer do; {ожиание момента изменения таймера}
x:=systimer;
end;
procedure stop;
begin
gettime(hour_stop, min_stop, sec_stop, hund_stop);
x:=systimer-x;
end;
procedure format;
procedure print(w: word);
begin
if w<10 then write('0');
write(w);
end;
begin
print(hour); write(':');
print(min); write(':');
print(sec); write('.');
print(hund);
writeln;
end;
procedure Report;
{Вывод на печать измеренного интервала в секундах и
сообщения через переменную Msg}
begin
write('Момент запуска: ');
format(hour_start, min_start, sec_start, hund_start);
write('Момент остановки: ');
format(hour_stop, min_stop, sec_stop,
hund_stop);
writeln(msg,' : ',x/182000:5:5,' cek.');
end; end.
-----------------------
(б)
