Программная реализация алгоритмов поиска в глубину и ширину в неориентированных графах

2) Поиск в ширину.

Начинаем поиск с любой вершины, например с х1. Соединяем ребрами вершину х1 со всеми смежными ей вершинами – х2, х4 и х9. Теперь по порядку рассматриваем эти смежные вершины. Берем вершину х2. Соединяем ее со всеми смежными ей вершинами, то есть с х3. Следующая по порядку вершины х4. Соединяем ее со всеми смежными вершинами, то есть с x5, x7 и x8. Затем по порядку идет ве

ршина х9, но соединить ее со смежной вершиной х8, мы не можем, так как полученный граф не будет являться остовом. Далее рассматриваем вершины х5, х7, и х8. У х5 есть смежная вершина х6. Соединяем их ребром. У вершин х7 и х8 нет таких смежных вершин. Таким образом, мы получили один из остовов графа G, изображенный на рисунке 13.

Рисунок 13 – Полученный граф

Рассмотренные алгоритмы могут быть использованы для построения всех остовных деревьев графа.

Заключение

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

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

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

Минимальные системные требования: Pentium 2 300 Mhz, 64 Mb RAM, 8 Mb Video Card. Объем 24, 6 кбайт. Операционная система Windows XP Professional Edition (работа программы так же возможна в операционных системах, начиная с MS DOS). Программа написана на языке Паскаль: Turbo Pascal 7.0.

Данная программа реализует алгоритмы поиска в глубину и ширину в неориентированных графах и осуществляет поиск в глубину и ширину в простом неориентированном графе с максимальным количеством вершин 15.

Список литературы

1 Белецкая С.Ю. Комбинаторика. Графы. Алгоритмы: Учеб. пособие. – Воронеж: ВГТУ, 2003. –103 с.

2 Емелина Е.И. Основы программирования на языке Паскаль. – М.: финансы и статистика, 1997. –208 с.: ил.

3 Емиличев В.А., Мельников О.И. Лекции по теории графов. – М.: Наука, 1990. –384 с.

4 Епашников А.М., Епашников В.А. Программирование в среде Turbo Pascal 7.0. –3-е изд., стер. – М.: «ДИАЛОГ-МИФИ», 1998. –288 с.

5 Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978. – 213 с.

6 Липский В. Комбинаторика для программистов: пер. с польск. – М.: Мир, 1998. – 213 с.

Приложение А

(обязательное)

Листинг программы

{$I-}

program Kursovaya_rabota;

uses crt;

var i, j, k, l, m, n, p: shortint;

q: char;

a: array [1 15,1 15] of shortint;

b, c:array [1 15] of shortint;

s: boolean;

label x;

procedure Vvod;

label w;

begin

w: repeat

writeln ('Vvedite celoe chislo vershin n (ot 1 do 15): ');

readln(n);

s:=IOResult=0;

if (not s) or (n<1) or (n>15)

then write (' Oshibka vvoda! ');

if (not s) or (n<1) or (n>15)

then until (n>0) and (n<16) and s;

writeln ('Vvedite simmetrichnuu matricu smejnosti (0 i 1)');

for k:=1 to n do

begin

for j:=1 to n do

begin

read (a [k, j]);

s:=IOResult=0;

if (not s) or (a [k, j]>1) or (a [k, j]<0)

then begin

write (' Oshibka vvoda! Vvedite celoe chislo vershin n (ot 1 do 15): ');

goto w;

end;

end;

readln;

end;

for k:=1 to n do

for j:=1 to n do

if a [k, j]<>a [j, k]

then begin

write (' Matrica ne simmetrihna! ');

goto w;

end;

end;

procedure Ochistka;

begin

clrscr;

writeln ('Kolichestvo vershin n=', n);

for k:=1 to n do

begin

for j:=1 to n do

write (' ', a [k, j]);

writeln;

b[k]:=1;

c[k]:=0;

end;

m:=0;

end;

procedure ishodnaja;

begin

repeat

writeln ('Vvedite celii nomer vershini, s kotoroi sleduet nachat poisk (ot 1 do n) ');

readln(i);

s:=IOResult=0;

if b[i]=0

then writeln ('Eta vershina uje bila rassmotrena ili ne suwestvuet.');

until (i>0) and (i<16) and (b[i]<>0) and s;

write ('poisk nachinaetca s ishodnoi zadannoi vershini ');

write ('X_', i);

writeln;

b[i]:=0;

l:=1;

p:=1;

c[l]:=i;

end;

procedure VShiriny;

begin

writeln ('…POISK V SHIRINY…');

ishodnaja;

for k:=1 to n do

if c[k]=0

then break

else begin

i:=c[k];

write ('prosmatrivaem vershinu X_', i, ' ');

for j:=1 to n do

if (a [i, j]=1) and (b[j]=1)

then begin

write (' k X_', i, ' prisoedinyaetca ');

write ('X_', j);

writeln;

b[j]:=0;

inc(l);

inc(p);

c[l]:=j;

end;

end;

if p=1

then write ('Eta vershina isolirovanna.');

writeln;

writeln ('… Poisk v shirinu dlya dostijimix vershin okonchen…');

end;

procedure VGlubiny;

label z;

begin

writeln ('…POISK V GLUBINY…');

ishodnaja;

repeat

z: i:=c[l];

for j:=1 to n do

if (a [i, j]=1) and (b[j]=1)

then begin

write (', iz nee spuskaemsya v ');

write ('X_', j);

b[j]:=0;

inc(l);

inc(p);

c[l]:=j;

goto z;

if l>1

then write ('eta vershina ischerpana');

writeln;

end;

dec(l);

until l=0;

if p=1

then write (' eta vershina izolirovana ');

writeln;

writeln ('… Poisk v glubinu dlya dostijimix vershin okonchen…');

end;

procedure vtorichnaja;

label y;

begin

y:if (n<>p) and (m<>p)

then begin

m:=0;

for j:=1 to n do

begin

c[j]:=0;

if b[j]=1

then begin

writeln (' vershina X_', j, ' ne dostijima ');

inc(m);

end;

end;

end

else m:=0;

while m<>0 do

begin

write ('S – poisk v shirinu, G – poisk v glubinu, ');

writeln ('N – izmenenie matrici, V – vixod iz programmi ');

q:=readkey;

case upcase(q) of

'G': begin

Ochistka;

VGlubiny;

goto y;

end;

'S': begin

Ochistka;

VShiriny;

 Скачать реферат