class NgLib:: MSTGraph(T)

• NgLib::MSTGraph(T)
• Reference
• Object

Overview

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

Kruskal 法による実装です。

Defined in:

Constructors

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

Class Method Summary

• .max (n)

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

• .min (n)

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

Instance Method Summary

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

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

• #size : Int64
• #sum

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

Constructor Detail

Class Method Detail

Instance Method Detail

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

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