最小木問題:
連結グラフ G=(V,E) と重み d:E->R+が与えられたとき、
最小木 T を求めよ。
クラスカルのアルゴリズム
- Set i=1 and let E0={}
- 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.
- 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
- Set i=1 and let E0={}
- 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.
- 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