Поиск в графе. Поиск в ширину и в глубину
Характеристика и сущность простых алгоритмов поиска и упорядочения элементов в графе. Выбор и содержание программирования, преимущества языка Pascal. Особенности поиска в ширину и в глубину, способы улучшения простых методов и описание алгоритма.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 28.04.2011 |
| Размер файла | 397,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Оглавление
- Аннотация 2
- 1. Выбор языка 3
- 2. Описание программы 4
- 2.1 Поиск в глубину 4
- 2.2 Поиск в ширину 4
- 3. Описание алгоритмов 6
- 3.1 Поиск в глубину 6
- 3.2 Поиск в ширину 6
- 4. Алгоритмы 8
- 4.1 Поиск в глубину 8
- 4.2 Поиск в ширину 11
Аннотация
При решении некоторых задач бывает нужно найти какой-то элемент в графе, или упорядочить его элементы.
В данной работе рассматриваются два алгоритма: поиск в ширину и в глубину. Два этих метода относятся к простым алгоритмам поиска. Существует несколько причин по которым желательно стоит их изучить.
Во-первых, на простых поиска можно изучить терминологию, связанную с графами.
Во-вторых, для многих задач, связанных с поиском в графе часто удобнее использовать простые методы.
В-третьих, некоторые из простых методов можно легко улучшить методов или использовать их для улучшения более сложных.
В-четвертых, большинство сложных методов поиска основано на измененных простых методах.
1. Выбор языка
Для реализации данных алгоритмов был выбран язык Pascal. Его основные преимущества заключаются в следующем:
· Многофункциональный и удобный отладчик;
· Хорошая справка- большинство полезных команд и многое другое подробно описаны;
· Высокая скорость компиляции, высокая скорость выполнения откомпилированных программ.
2. Описание программы
2.1 Поиск в глубину
Один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
Посмотрите на рисунок ниже.
2.2 Поиск в ширину
Один из методов обхода графа Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам -- метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д. Это видно на рисунке ниже.
3. Описание алгоритмов
3.1 Поиск в глубину
Рассмотрим пример работы алгоритма на графе ниже.
|
1-й шаг |
Идем от первой вершины в “глубь” графа. Пометим её вершину второй. |
|
|
2-й шаг |
То же самое со второй вершиной. Так появится третья вершина. |
|
|
3-й шаг |
Аналогично появилась четвертая вершина. |
|
|
4-й шаг |
Из четвертой вершины некуда идти, так что возвращаемся в третью. Нам есть куда идти. Появилась пятая вершина. |
|
|
5-й шаг |
Из пятой некуда идти, из третей- тоже. Возвращаемся во вторую. Идем в шестую вершину. |
|
|
6-й шаг |
Теперь возвращаемся во вторую, а затем и в первую вершину. |
|
|
7-й шаг |
Теперь пытаемся пойти в другую вершину из первой. В седьмую. |
|
|
8-й шаг |
Из неё идем в восьмую вершину. |
|
|
9-й шаг |
Теперь нам некуда идти. Возвращаемся в седьмую. И теперь идем в девятую. Все вершины обошли. |
3.2 Поиск в ширину
Рассмотрим тот же граф, но теперь используя поиск в ширину:
|
1-й шаг |
Из первой вершины идем в смежные и помечем их соответственно второй и третьей. |
|
|
2-й шаг |
Из второй вершины идем в смежные. Помечаем четвертой и пятой. |
|
|
3-й шаг |
Из третьей вершины идем в шестую и седьмую. |
|
|
4-й шаг |
Из четвертой вершины идем в восьмую и девятую. Так как из пятой, шестой и седьмой идти некуда, то граф обойден. |
4. Алгоритмы
4.1 Поиск в глубину
const
MaxN=10;
type
pt=^elem;
elem=record
data:integer;
next:pt;
end;
var
a:array[1..maxn] of pt;
b:array[1..maxn] of boolean;
num:array[1..maxn] of integer;
n,cnt:integer;
procedure insertelem(var t:pt;x:integer);
var t2:pt;
begin
if t=nil then begin
new(t);
t^.data:=x;
t^.next:=nil;
end
else begin
t2:=t;
while t2^.next<>nil do
t2:=t2^.next;
new(t2^.next);
t2^.next^.data:=x;
t2^.next^.next:=nil;
end;
end;
procedure init;
var i,j,w,q:integer;
begin
cnt:=0;
assign(input,'input.txt');
reset(input);
readln(input,n);
for i:=1 to n do begin
a[i]:=nil;
b[i]:=true;
num[i]:=0;
end;
for i:=1 to n do begin
read(input,q);
for j:=1 to q do begin
read(input,w);
insertelem(a[i],w);
end;
end;
close(input);
end;
procedure incnum(v:integer);
begin
inc(cnt);
num[cnt]:=v;
end;
procedure searchdepths(v:integer);
var t:pt;
begin
b[v]:=false;
t:=a[v];
while t<>nil do begin
if b[t^.data] then begin
incnum(t^.data);
searchdepths(t^.data);
end;
t:=t^.next;
end;
end;
procedure print;
var i:integer;
begin
assign(output,'output.txt');
rewrite(output);
for i:=1 to n do
write(output,num[i],' ');
close(output);
end;
begin
init;
incnum(1);
searchdepths(1);
print;
end.
4.2 Поиск в ширину
граф алгоритм программирование поиск рascal
const
MaxN=10;
type
pt=^elem;
elem=record
data:integer;
next:pt;
end;
var
a:array[1..maxn] of pt;
b:array[1..maxn] of boolean;
num,quie:array[1..maxn] of integer;
n,cnt,k:integer;
procedure insertelem(var t:pt;x:integer);
var t2:pt;
begin
if t=nil then begin
new(t);
t^.data:=x;
t^.next:=nil;
end
else begin
t2:=t;
while t2^.next<>nil do
t2:=t2^.next;
new(t2^.next);
t2^.next^.data:=x;
t2^.next^.next:=nil;
end;
end;
procedure init;
var i,j,w,q:integer;
begin
cnt:=0;
assign(input,'input.txt');
reset(input);
readln(input,n);
for i:=1 to n do begin
a[i]:=nil;
b[i]:=true;
num[i]:=0;
quie[i]:=0;
end;
for i:=1 to n do begin
read(input,q);
for j:=1 to q do begin
read(input,w);
insertelem(a[i],w);
end;
end;
close(input);
end;
procedure incnum(v:integer);
begin
inc(cnt);
num[cnt]:=v;
end;
procedure add(v:integer);
var i:integer;
begin
i:=1;
repeat
if quie[i]=0 then begin
quie[i]:=v;
exit;
end;
inc(i);
if (i>n) then
exit;
until false;
end;
procedure searchwidth(var k:integer);
var t:pt;
begin
t:=a[quie[k]];
while t<>nil do begin
if b[t^.data] then begin
b[t^.data]:=false;
add(t^.data);
end;
t:=t^.next;
end;
incnum(quie[k]);
inc(k);
if k>n then
exit;
searchwidth(k);
end;
procedure print;
var i:integer;
begin
assign(output,'output.txt');
rewrite(output);
for i:=1 to n do
write(output,num[i],' ');
close(output);
end;
begin
init;
k:=1;
quie[1]:=1;
b[1]:=false;
searchwidth(k);
print;
end.
Размещено на Allbest.ru
Подобные документы
Понятие алгоритма как набора инструкций, описывающего порядок действий. Поиск в ширину - метод обхода графа и поиска пути в нем. Пример работы алгоритма поиска в ширину, его неформальное и формальное описание. Реализация с помощью структуры "очередь".
курсовая работа [684,8 K], добавлен 05.04.2015Поиск как основа функционирования СОЗ. Стратегии; эвристического поиска и управления выводом. Циклическая работа интерпретатора. Вывод на знаниях в продукционных системах. Методы поиска в глубину и ширину. Формализация задач в пространстве состояний.
презентация [741,2 K], добавлен 14.08.2013Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.
курсовая работа [411,6 K], добавлен 25.04.2013Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [22,8 K], добавлен 16.09.2013Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.
реферат [929,8 K], добавлен 23.09.2013Способ представления графа в информатике. Алгоритмы поиска элементарных циклов в глубину в неориентированных графах. Описание среды wxDev-C++, последовательность создания проекта. Руководство пользователю программы поиска и вывода на экран простых циклов.
курсовая работа [783,2 K], добавлен 18.02.2013Особенности и преимущества языка C#. Алгоритмы поиска маршрутов в графе. Разработка вычислительной системы транспортной логистики на языке C#. Выбор среды разработки, визуализация транспортной сети. Задание условий поиска и пример работы алгоритма.
дипломная работа [457,1 K], добавлен 24.06.2015Понятие и базовые свойства ориентированного дерева. Обходы (способы нумерации вершин) в глубину и ширину. Представление бинарных графов с помощью указателей и массива, скобочной записи, списком прямых предков. Сбалансированность дерева двоичного поиска.
презентация [330,6 K], добавлен 19.10.2014Разработка программы, находящей эйлеров путь в графе с количеством вершин n от 2 до 20. Входные и выходные данные. Алгоритм поиска эйлерова пути с возвратом массива, содержащего результат. Описание модулей. Проектирование тестов методами черного ящика.
курсовая работа [89,9 K], добавлен 25.02.2012Обзор алгоритмов распознания объектов на двумерных изображениях. Выбор языка программирования. Обнаружение устойчивых признаков изображения. Исследование алгоритмов поиска объектов на плоскости. Модификация алгоритма поиска максимума дискретной функции.
дипломная работа [1,0 M], добавлен 16.06.2013
