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

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

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. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


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

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

Образование соседних чисел Фрагмент: Программная задача: показать образование числа 4 и числа 3 друг из друга...

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

Различие эмпиризма и рационализма Родоначальником эмпиризма стал английский философ Ф. Бэкон. Основной тезис эмпиризма гласит: в разуме нет ничего такого...

Индекс гингивита (PMA) (Schour, Massler, 1948) Для оценки тяжести гингивита (а в последующем и ре­гистрации динамики процесса) используют папиллярно-маргинально-альвеолярный индекс (РМА)...

Методика исследования периферических лимфатических узлов. Исследование периферических лимфатических узлов производится с помощью осмотра и пальпации...

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