Code666 (代码贴、代码片段)

[Delphi (Object Pascal)] pascal经典算法 - 最小生成树Kruskal算法(贪婪) →→→→→进入此内容的聊天室

来自 , 2019-05-13, 写在 Delphi (Object Pascal), 查看 109 次.
URL http://www.code666.cn/view/ef452c63
  1.  
  2. function find(v: Integer): Integer; {返回顶点v所在的集合}
  3. var
  4.   i: Integer;
  5. begin
  6.   i := 1;
  7.   while (i <= n) and (not v in vset[i]) do
  8.     Inc(i);
  9.   if i <= n then
  10.     find := i
  11.   else
  12.     find := 0;
  13. end;
  14.  
  15. procedure kruskal;
  16. var
  17.   tot, i, j: Integer;
  18. begin
  19.   for i := 1 to n do
  20.     vset[i] := [i];{初始化定义n个集合，第I个集合包含一个元素I}
  21.   p := n - 1;
  22.   q := 1;
  23.   tot := 0; {p为尚待加入的边数，q为边集指针}
  24.   Sort;
  25.   {对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}
  26.   while p > 0 do
  27.   begin
  28.     i := find(e[q].v1);
  29.     j := find(e[q].v2);
  30.     if i <> j then
  31.     begin
  32.       Inc(tot, e[q].Len);
  33.       vset[i] := vset[i] + vset[j];
  34.       vset[j] := [];
  35.       Dec(p);
  36.     end;
  37.     Inc(q);
  38.   end;
  39.   Writeln(tot);
  40. end;
  41. //delphi/6605

回复 "pascal经典算法 - 最小生成树Kruskal算法(贪婪) "

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666