Kruskal法

今回はクラスカル法(Kruskal法)のプログラムに挑戦したのだが、Prim法に比べてプログラム作成には苦戦した。Kruskal法はPrim法と同じく最小全域木(MST)を求めるためのアルゴリズムで、Prim法と異なり、グラフが連結でない場合にも利用出来る。しかし、今回のプログラムでは連結でないグラフは考慮していない。

最初、wikiの例を見てアルゴリズムの動作を確認していたのだが、新しく辺を追加して、頂点が同じ木に所属するとなった際の動作が自分にはどうもわからない。(疑似コードとかついてるけど読む気になれない)

そこで、Google頼りにさらに調査を続けた結果、どうやらUnion-Findなるデータ構造を使えば木と辺の統合を効率的に記述出来るらしいことが判明。Union-Findの実装にはこのページを参考にさせてもらった。Union-Findの実装が済むとKruscal法の実装はすぐ出来た。

胆になる部分は、「コストが小さい辺から順に、木に統合出来る場合は結果の辺リストに加える」という操作で、プログラムでは以下の部分に相当。木に統合できるかどうか、という部分でUnion-Findを使っている。

for i in adj do
    let (f,t,c) = i in
    if uf.union f t then
        edges.Add(i)
done;;

以下、今回作成したコード

#light "off"

open Microsoft.FSharp.Collections;;
let pe x = print_any x;print_endline "";;

//Kruskal法(Union-Findを利用)

//Union-Findクラス
type UnionFind = class
    val data : ResizeArray<int>
    new (size:int) as x = {data = new ResizeArray<int>(size)} then
        //-1で初期化
        for i=1 to size do x.data.Add(-1) done
    member private x.root n =
        let rec aux n =
            //経路圧縮なし
            //if x.data.[n] < 0 then n else aux (x.data.[n])
            //経路圧縮あり
            if x.data.[n] < 0 then n else begin x.data.[n] <- aux (x.data.[n]);x.data.[n] end
        in aux n
    member x.find a b = x.root(a) = x.root(b)
    member x.union a b =
        let src = x.root(a) in
        let dst = x.root(b) in
        if src < dst then begin
            x.data.[src] <- x.data.[src] + x.data.[dst];
            x.data.[dst] <- src;
            end
        else if src > dst then begin
            x.data.[dst] <- x.data.[src] + x.data.[dst];
            x.data.[src] <- dst;
            end;
        src <> dst
    end;;
//ノード数
let nodenum = 6;;
//辺リスト
let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];;
//辺の重みの小さい順にソート
let sorter a b = let ((_,_,l),(_,_,r))=(a,b) in
    if l>r then 1 else if l<r then -1 else 0 in
Array.sort sorter adj;;

let uf = new UnionFind(nodenum);;
//結果を入れる辺リスト
let edges = new ResizeArray<int*int*int>();;
//辺の重みの小さい順に処理
for i in adj do
    let (f,t,c) = i in
    if uf.union f t then
        edges.Add(i)
done;;

for i in edges do pe i done;

//↑ここまでのプログラムでも動作する



//以下前回と同じ
open Microsoft.FSharp.Core;;
open System;;
open System.Windows.Forms;;
open System.Drawing;;

//要素数と(始点、終点、コスト)の配列を受け取り、そのグラフを表示するクラス
type Graph = class inherit Form
	val pbox : PictureBox
	val pos : (float32*float32) array   //各ノードのx,y座標
	val circle_width : float32          //1つのノードの幅
	val circle_height : float32         //1つのノードの高さ
	new (pnum:int,adj) as this =
	    {pbox = new PictureBox();
	     pos=Array.init pnum (fun x -> (0.f,0.f));
	     circle_width = 50.f;
	     circle_height = 50.f;}
		then
		let (whole_width,whole_height)=(800,600) in
		this.Width <- whole_width;
		this.Height <- whole_height;
		let (screen_width,screen_height)=(this.ClientRectangle.Width,this.ClientRectangle.Height) in
		this.pbox.Dock <- DockStyle.Fill;
		this.Controls.Add(this.pbox);
		this.pbox.Image <- new Bitmap(screen_width,screen_height);
		//画面中央の計算
		let (cx,cy)=((Float32.of_int screen_width)/2.f,(Float32.of_int screen_height)/2.f) in
		//各ノードの座標計算
		for i=0 to pnum-1 do
		    let dist = 200.f in
		    let (dx,dy)=
		    (cx+dist*Float32.of_float(Math.Cos(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i))),
		     cy+dist*Float32.of_float(Math.Sin(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i)))) in
		     this.pos.[i]<-(dx,dy);
		done;
		//ノードを描く
		Array.mapi (fun i x -> this.circle (fst x) (snd x) (i.ToString())) this.pos |> ignore;
		//ノード間の接続とコストを描く
        for i in adj do
            let (s,e,c) = i in
            this.line (fst this.pos.[s]) (snd this.pos.[s]) (fst this.pos.[e]) (snd this.pos.[e]) (Float32.of_int c)
            done
		
    //円とラベルを指定座標に描く
    member this.circle (x:float32) (y:float32) label =
		use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in
		let w,h = (this.circle_width,this.circle_height) in
		g.DrawEllipse(Drawing.Pens.Black,x,y,w,h);
		let font = new Font("MS UI Gothic",18.f) in
		let size = g.MeasureString(label,font,768,new StringFormat()) in
		g.DrawString(label,font,Brushes.Black,x+w/2.f-size.Width/2.f,y+h/2.f-size.Height/2.f);

    //線を指定座標から指定座標へ描き、間にコストを描く
    member this.line (sx:float32) (sy:float32) (ex:float32) (ey:float32) c=
        use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in
        let (dx,dy) = (this.circle_width/2.f,this.circle_height/2.f) in
		let font = new Font("MS UI Gothic",12.f) in
		let (nsx,nsy,nex,ney) = (sx+dx,sy+dy,ex+dx,ey+dy) in
        g.DrawLine(Pens.Black,nsx,nsy,nex,ney);
        //線を1:2に内分する点にコストを描く
		g.DrawString(c.ToString(),font,Brushes.Black,(nsx+2.f*nex)/3.f,(nsy+2.f*ney)/3.f);
end;;


[<STAThread>]
do System.Windows.Forms.Application.Run(new Graph(6,edges));;