VPF::[Pascal] "Алгоритм прима" - Форум программистов

Вожык

Дата 21.12.2006, 01:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 21.12.2006

Репутация: нет
Всего: нет

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

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

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

Алгоритм.

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

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

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

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

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

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

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

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

Rodman

Дата 22.12.2006, 11:14 (ссылка)

(нет голосов)

Загрузка ...

CIO

Профиль
Группа: Участник
Сообщений: 6144
Регистрация: 7.5.2006
Где: Ukraine ⇛ Kyiv ci ty

Репутация: 26
Всего: 122

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

Код


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.

--------------------

CRM с функцией АвтоОбзвона

Лотереи мира

Emily

Дата 20.5.2007, 18:44 (ссылка)

(нет голосов)

Загрузка ...

pure dream

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 19.3.2007
Где: Украина

Репутация: нет
Всего: нет

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

yaron

Дата 13.4.2011, 18:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 13.4.2011

Репутация: нет
Всего: нет

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

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »