Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

while notRow_IsVisited(Visited) do





for var i:=1 to N do if not Visited[i] then DepthSearch(i);

delete(Path, 1, 2);

writeln('Путь обхода: ', Path);

end;

 

function minf(x, y: integer): integer;

Begin

if x > y then minf:=y else minf:=x;

end;

 

//определить кратчайший путь из заданной вершины во все остальные

procedure Path_Short(g: TAdMatrix; x: byte);

Const

max = 1000000;

Var

d, s, p: TIList;

min, z, k: integer;

Begin

write('Введите вершину для нахождения кратчайшего пути от нее ко всем остальным: ');

readln(x);

min:=1000;

z:=1;

for var i:=1 to n do

for var j:=1 to n do

if (i <> j) and (g[i, j] = 0) then g[i,j]:=max;

for var i:=1 to n do

Begin

s[i]:=0;

d[i]:=g[x,i];

p[i]:=1;

end;

s[x]:=1;

p[x]:=0;

for var i:=1 to n do

Begin

for var j:=1 to n do

if (d[j] < min) and (d[j] <> 0) and (s[j] = 0) then

Begin

min:=d[j];

z:=j;

end;

s[z]:=1;

for k:= 1 to n do

if s[k]=0 then

Begin

d[k]:=minf(d[k], d[z] + g[z,k]);

p[k]:=k;

end;

min:=1000;

end;

for var i:=1 to n do write(i:2,' ');

write(' - Вершины графа');

writeln();

for var i:=1 to n do write(d[i]:2,' ');

write('- Кратчайшие расстояния');

writeln;

end;

 

//построение минимального остовного дерева

procedure OstovTree_Prim(g: TAdMatrix; var u: TIList);

Var

i,j,z,min,mi,mj,f,f2,tmp: byte;

vu, u1: TIList;

Begin

write('Введите вершину с которой следует начать построение: ');

readln(z);

min:=100;

f:=0;

f2:=0;

for i:=1 to n do

Begin

vu[i]:=1;

u[i]:=0;

u1[i]:=0;

end;

u[z]:=1;

u1[z]:=1;

vu[z]:=0;

i:=1;

z:=2;

while z <= n - f2 do

Begin

for i:=1 to n - f2 do if u1[i] = 1 then

for j:=1 to n - f2 do if (g[i, j] < min) and (g[i, j] > 0) and (u1[j] = 0) then

Begin

min:=g[i,j];

mi:=i;

mj:=j;

end;

u[mj]:=z;

u1[mj]:=1;

g[mi, mj]:=0;

g[mj, mi]:=0;

inc(z,1);

min:=100;

end;

for i:=1 to n do write(i:2,' ');

writeln(' - Вершины графа');

for i:=1 to n do

Begin

write(u[i]:2, ' ');

tmp:=tmp + u[i];

end;

writeln(' - Порядок их добавления в остовное дерево');

write('Суммарный вес - ',tmp);

writeln('');

end;

 

//вывод меню

procedure Menu;

Var

MI, a: integer;

Begin

writeln('');

writeln('=========================================================');

writeln('Выберите действие: ');

writeln('1. Загрузить граф из файла.');

writeln('2. Определение самого короткого цикла в графе.');

writeln('3. Выполнить обход графа в глубину.');

writeln('4. Определить кратчайший путь из заданной вершины во все остальные.');

writeln('5. Построить минимальное остовное дерево с помощью алгоритма Прима.');

writeln('6. Выход из программы.');

write('Введите номер действия: ');

readln(MI);

CaseMI of

1: begin write('Введите номер графа: '); readln(a); OpenFile(a, Gr); writeln('Граф загружен!'); Menu; end;

2: begin Find_ShortLoop(Gr); Menu; end; //Нахождение короткого цикла

3: begin write('Введите номер вершины, с которой необходимо начать обход: '); readln(a); Share_Deep(Gr, a); Menu; end; //Обход графа в глубину

4: begin Path_Short(Gr, 1); Menu; end; //Определение кратчайшего пути из заданной вершины во все остальные

5: begin OstovTree_Prim(Gr, Mot); Menu; end; //Построение минимального остовного дерева

6: exit;

end;

end;

 

Begin

//загружаем файл

OpenFile(0, Gr);

//отображаем меню

Menu;

end.







Дата добавления: 2015-06-15; просмотров: 409. Нарушение авторских прав; Мы поможем в написании вашей работы!




Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...


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


Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

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

РЕВМАТИЧЕСКИЕ БОЛЕЗНИ Ревматические болезни(или диффузные болезни соединительно ткани(ДБСТ))— это группа заболеваний, характеризующихся первичным системным поражением соединительной ткани в связи с нарушением иммунного гомеостаза...

Решение Постоянные издержки (FC) не зависят от изменения объёма производства, существуют постоянно...

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

Броматометрия и бромометрия Броматометрический метод основан на окислении вос­становителей броматом калия в кислой среде...

Метод Фольгарда (роданометрия или тиоцианатометрия) Метод Фольгарда основан на применении в качестве осадителя титрованного раствора, содержащего роданид-ионы SCN...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия