最小木問題:

連結グラフ G=(V,E) と重み d:E->R+が与えられたとき、 最小木 T を求めよ。

クラスカルのアルゴリズム

  1. Set i=1 and let E0={}
  2. Select an edge ei of minimum value not in Ei-1 such that Ti=<Ei-1 cup {ei} >is acyclic and define Ei=Ei-1 cup {ei}. If no such edge exists, Let T=<Ei>and stop.
  3. Replace i by i+1. Return to Step 2.
クラスカルのアルゴリズムが要する計算時間はO(|E|log|V|)である。

JavaScript ソースファイル:

JavaScript デモ

関連ページ:

MST Problem:

Given a connected graph G=(V,E) and a weight d:E->R+, find a minimum spanning tree T.

Kruskal's Algorithm

  1. Set i=1 and let E0={}
  2. Select an edge ei of minimum value not in Ei-1 such that Ti=<Ei-1 cup {ei} >is acyclic and define Ei=Ei-1 cup {ei}. If no such edge exists, Let T=<Ei>and stop.
  3. Replace i by i+1. Return to Step 2.
The time required by Kruskal's algorithm is O(|E|log|V|).

JavaScript Source Files:

JavaScript Demos

See Also