class NgLib::BinaryBfsGraph

Defined in:

#add_edge(u : Int, v : Int, w : Int, directed : Bool = true)
辺 $(u, v, w)$ を追加します。
#graph : Array(Array(Edge))
#shortest_path(start : Int, dest : Int)
始点 start から終点 dest への最短経路長を返します。
#shortest_path(start : Int)
始点 start から各頂点への最短経路長を返します。
#shortest_path
全点対間の最短経路長を返します。
#size : Int32

def self.new(n : Int) #

$n$ 頂点 $0$ 辺からなるグラフを作成します。

graph = BfsGraph.new(n)

[View source]

def add_edge(u : Int, v : Int, w : Int, directed : Bool = true) #

辺 $(u, v, w)$ を追加します。

$w$ は $0$ または $1$ である必要があります。

directed が true の場合、有向辺とみなして、$u$ から $v$ への辺のみ生やします。

graph = BfsGraph.new(n)
graph.add_edge(u, v)                 # => (u) <---w---> (v)
graph.add_edge(u, v, directed: true) # => (u) ----w---> (v)

[View source]

def graph : Array(Array(Edge)) #

[View source]

def shortest_path(start : Int, dest : Int) #

始点 start から終点 dest への最短経路長を返します。

dist = graph.shortest_path(start: 2, dest: 0)
dist # => 12

[View source]

def shortest_path(start : Int) #

始点 start から各頂点への最短経路長を返します。

dist = graph.shortest_path(start: 2)
dist # => [3, 8, 0, 7, 1]

[View source]

def shortest_path #

全点対間の最短経路長を返します。

dists = graph.shortest_path
dists # => [[0, 1, 3], [1, 0, 2], [1, 1, 0]]

[View source]

def size : Int32 #

[View source]