Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.06.2011, 02:33   #1
Klik_1602
Пользователь
 
Аватар для Klik_1602
 
Регистрация: 06.09.2010
Сообщений: 51
По умолчанию Алгоритм Краскала

Помогите разобраться в коде - алгоритм построения минимального остовного дерева в связаном графе - Алгоритм Краскала. Код у меня есть - нужны только пояснения к нему, помогите пожалуйста..
вот код..
Код:
program minim_tree_kraskal;
const maxn=100;
var p:array[1..3,1..maxn*(maxn-1) div 2]of integer;
    Mark:array[1..maxn]of integer;
    k,i,t:integer;
    m,n:integer;{m - rebra;n - vershini }

procedure Change_Mark(l,m:integer);
var i,t:integer;
begin
   if m < l then
      begin
         t:=l;l:=m;m:=t;
      end;
   for i:=1 to n do
      if Mark[i]=m then Mark[i]:=l;
end;

begin
   readln(n,m);
   for i:=1 to m do
      read(p[1,i],p[2,i],p[3,i]);
   for i:=1 to m-1 do
      for t:=i+1 to m do
         if p[3,i] > p[3,t] then
            begin
               k:=p[1,i];p[1,i]:=p[1,t];p[1,t]:=k;
               k:=p[2,i];p[2,i]:=p[2,t];p[2,t]:=k;
               k:=p[3,i];p[3,i]:=p[3,t];p[3,t]:=k;
            end;
   for i:=1 to n do mark[i]:=i;
   k:=0;t:=m;
   while k < n-1 do
      begin
         i:=1;
         while (i <= t) and (Mark[p[1,i]] = Mark[p[2,i]]) and (p[1,i] <> 0) do inc(i);
         inc(k);

         if p[1, i] * p[2, i] <> 0 then begin { Добавлена проверка на ненулевые вершины }
            write(p[1,i],' ',p[2,i],'  ');
            change_Mark(Mark[p[1,i]],Mark[p[2,i]]);
         end;
      end;
end.
Klik_1602 вне форума Ответить с цитированием
Старый 21.06.2011, 15:59   #2
Merkator
Читаю Кормена
Пользователь
 
Аватар для Merkator
 
Регистрация: 28.12.2008
Сообщений: 46
По умолчанию

Рекомендую к изучению 2 ссылки. Думаю они вам помогут в понимании программы:
http://e-maxx.ru/algo/mst_kruskal
http://e-maxx.ru/algo/mst_kruskal_with_dsu
Merkator вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
прима-краскала salwator Паскаль, Turbo Pascal, PascalABC.NET 0 03.06.2011 22:17
Алгоритм TMDS (Алгоритм передачи данных интерфейса DVI) Pro4RE Помощь студентам 2 24.04.2011 21:55
алгоритм краскала Олександр17 Помощь студентам 0 02.12.2010 19:59
Как проверить граф на связанность? Алгоритм Краскала PasSuper Общие вопросы C/C++ 10 18.01.2010 10:13
Алгоритм Краскала anGeee Паскаль, Turbo Pascal, PascalABC.NET 0 17.12.2008 18:16