浅谈最小生成树

    xiaoxiao2021-03-26  13

    ##简介

    Kruskal(克鲁斯卡尔)算法是一种巧妙利用并查集来求最小生成树的方法。首先我们把无向图中互相连通的一些点成为处于同一连通块的。Kruskal算法将一个连通块仿作一个集合。Kruskal首先将所有的边按从小到大的顺序排序,并认为每一个点都是孤立的,分属于n个独立的集合。然后按顺序美剧每一条边。如果这条边链接着两个不同的集合,就把这两条边加入最小生成树,这两个不同的集合就合并了;如果这条边连接的两点属于同一集合,就跳过,直到选到n-1条边为止。

    ##算法描述

    初始化并查集,father[x]=xtot=0将所有边用快排从小到大排序for i=1~n // 循环所有已从小到大排序的边 if 这是一条u,v不属于统一集合的边(u,v) begin 合并u,v左右的集合,相当于把边(u,v)加入最小生成树 tot:=tot+w(u,v) k+1 如果k=n-1,说明最小生成树已形成,则break end; ##代码 var x,y:array[0..2000]of longint; z,x1,y1:array[0..4000000]of longint; i,j,n,m,ans,k,max,min,xx,yy,t:longint; father:array[0..2000]of longint; procedure kp(l,r:longint);//快排 var i,j,mid:longint; begin i:=l; j:=r; mid:=z[(l+r) div 2]; while i<=j do begin while z[i]<mid do inc(i); while z[j]>mid do dec(j); if i<=j then begin x[0]:=x[i]; x[i]:=x[j]; x[j]:=x[0]; y[0]:=y[i]; y[i]:=y[j]; y[j]:=y[0]; z[0]:=z[i]; z[i]:=z[j]; z[j]:=z[0]; inc(i); dec(j); end; end; if l<j then kp(l,j); if r>i then kp(i,r); end; function get(x:longint):longint;//找父亲 begin if father[x]=x then exit(x); father[x]:=get(father[x]); exit(father[x]); end; procedure hbfather(x,y:longint);//合并父亲 var fx,fy:longint; begin fx:=get(x); fy:=get(y); if fx<>fy then father[fx]:=father[fy]; end; begin readln(n,m); for i:=1 to n do readln(x[i],y[i],z[i]); kp(1,n);//排序 for j:=1 to n do father[j]:=j; k:=0; min:=0; for i:=1 to t do begin if get(x[i])<>get(y[i]) then begin hbfather(x[i],y[i]); ans:=ans+z[i]; inc(k); end; if k=n-1 then break; end; if ans=maxlongint then writeln(-1) else writeln(ans); end.
    转载请注明原文地址: https://ju.6miu.com/read-600430.html

    最新回复(0)