Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Pascal] "Алгоритм прима"

Автор: Вожык 21.12.2006, 01:28

Вот краткое описание алгоритма:
Формулировка задачи. Дан взвешенный граф, в котором веса присвоены ребрам. Необходимо найти минимальное остовное дерево имеющую своим корнем одну из вершин графа.

Идея алгоритма. Пусть часть остовного дерева уже построена. Это утверждения всегда верно, так как в начале процесса вершина с которой начинается построение уже входит в дерево. Итак если часть основного дерева уже есть, то множество вершин графа можно разделить на два подмножества: подмножество состоящее из вершин уже построенного остовного дерева и оставшихся вершин графа.

Очевидно, что среди ребер соединяющихся эти два множества существует ребро наименьшего веса. Можно доказать, (но мы здесь этого делать не будем) что минимальное дерево проходит через это ребро.

Алгоритм.

§        Множество остовных вершин – исходная веришны

§        Множество оставшихся  - все вершины за исключением исходной.

§        Пока множество оставшихся не пусто

o       Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.

o       Для найденного ребра, вершину принадлежащую множеству оставшихся:

§        Вычеркиваем из множества оставшихся.

§        Добавляем к множеству остовных.

Мне необходимо чтоб граф создавал сам пользователь(т.е сам его задавал) и  уже по этому графу выполнялся поиск остовного дерева.
Программа нужна очень срочно, ибо через 2 дня сдавать курсовой, а я в делфи можно сказать чайник...
Я видел уже подобный топик, но решил создать свой,т.к там был выдан код на паскале, а мне нужно срочно именно в делфи...заранее благодарен!

Автор: Rodman 22.12.2006, 11:14

вот основа алгоритма, но на обычном Паскале

Код


Program prim;
uses Crt;
var
 a:array[1..100,1..100] of integer;
 t,min,x,y,u,i,j,k,l,m,n,cost:longint;
 b,c:array[1..100] of integer;
begin
 clrscr;
 writeln;
 writeln('Lab Work #8 - Raschet Minimalynogo Puti ( Algoritm Prima ):');
 write('Vvedite Razmer Massiva: ');
 readln(n);
 for i:=1 to n do
  for j:=1 to n do a[i,j]:=32000;
 writeln('Vvedite Kolichestvo Vvodimih Elementov: ');
 readln(m);
 for i:=1 to m do
 begin
   Writeln('Vvedite Aderess(x,y) i Harakteristiku #',i,':');
   readln(k,l,cost);
   a[k,l]:=cost;
   a[l,k]:=cost;
  end;
 k:=0;
 u:=1;
 c[1]:=1;
 b[u]:=1;
 while u<n do
  begin
   min:=32000;
   for i:=1 to u do
   if b[i]>0 then
   begin
    t:=b[i];
    for j:=1 to n do
      if (a[t,j]<min) and (c[j]=0) then begin min:=a[t,j]; y:=t; x:=j; end;
   end;
   inc(u);
   b[u]:=x;
   c[x]:=1;
   k:=k+a[y,x];
   a[y,x]:=32000;
   a[x,y]:=32000;
  end;
 Writeln('Rezultat: ',k);
 readkey;
end.

Автор: Emily 20.5.2007, 18:44

Обьясни пожалуйста что значит в етой программе "Vvedite Razmer Massiva", "Vvedite Kolichestvo Vvodimih Elementov","Vvedite Aderess(x,y) i Harakteristiku #" и что она выводит как результат .Буду очень благодарна! smile

Автор: yaron 13.4.2011, 18:15

Цитата(Emily @ 20.5.2007, 18:44)

Меня тоже интересует этот вопрос. Помогите пожалуйста