Thuật toán Kruskal

thuật toán Kruskal
Procedure Kruskal_Algorithm; Begin K:= Æ ; While (joinedEdges < n-1) or (E = Æ ) do Begin GetEdges(x,y);{Lấy từ E đã sắp tăng dần trọng số} If not creatCycle(x,y) then Begin Union(x,y); {Thủ tụcTạo `dad`} (x,y)->K; {Kết nạp cạnh (x,y) vào K} End; End; If joinEdges=n-1 then FoundTree else notFoundTree; End; Thủ tục này bằng Pascal như sau: procedure KRUSKAL_Algorithm; var i: integer; begin i:=1; numEdge:=0; W:=0;{Weight} repeat while creatCycle(e[i,1],e[i,2]) and (i<=m) do inc(i); if (i>m) or (numEdge>=n-1) then break; inc(numEdge); BE[numEdge,1]:=e[i,1]; BE[numEdge,2]:=e[i,2]; W:=W+e[i,3]; until false; end; Thuật toán Prim
Procedure Prim_Algorithm; Begin VH:={rootPrim}; {Bất kỳ!} T:= Æ ; While |VH| < n do Begin FindMinEdge(u,v); v->VH; {Kết nạp đỉnh v vào v} (u,v)->T; {Kết nạp cạnh (u,v) vào K} End; End; - Khi lập trình để dễ dàng tìm được cặp (u,v) nhỏ nhất như vậy chúng ta sử dụng các mảng phụ trợ đặc biệt. Thủ tục đó bằng Pascal như sau: procedure PRIM_Algorithm; var j,u: integer; begin numEdge:=0; W:=0; orderPrim[1]:=rootPrim; repeat u:=0; for j:=1 to n do if (over[j]=0) and ( đ[j] if u=0 then break; { Ađ u:} over[u]:=1; inc(numEdge); orderPrim[numEdge+1]:=u; BE[numEdge,1]:=linkfrom[u]; BE[numEdge,2]:=u; W:=W+a[u,linkfrom[u]]; {Update from u:} for j:=1 to n do if (over[j]=0) and (a[u,j]>0) and ( đ[j]>a[u,j]) then begin đ [j]:=a[u,j]; linkfrom[j]:=u; end; until false; end;