class

NgLib::MSTGraph(T)

Inherits Reference < Object

$n$ 頂点の重み付きグラフについて、最小/最大全域木を構築します。

Kruskal 法による実装です。

Constructors

new(n)
Source
new(n, &cmp : T, T -> Int32)
Source

Class methods

max(n)

$n$ 頂点 $0$ 辺のグラフを生成します。

最大全域木を構築します。

Source
min(n)

$n$ 頂点 $0$ 辺のグラフを生成します。

最小全域木を構築します。

Source

Instance methods

add_edge(u : Int, v : Int, w : T)

グラフに辺 $(u, v, w)$ を追加します。

graph = MSTGraph(Int64).new(n) { |a, b| a < b }
m.times { graph.add_edge(u, v, w) }
Source
size
Source
sum

最小全域木を構成したときの辺の重みの総和求めます。

graph = MSTGraph(Int64).new(n) { |a, b| a < b }
m.times { graph.add_edge(u, v, w) }
graph.sum
Source