Javaで割り算の天井関数は以下のように実装できる。Math.ceilもあったんだけど、ちょっと挙動が違った。 として、 床関数 は普通に x/d でよい 。端数は切り捨てられるため。 余談 ちなみに で、 を満たす最小の整数 を求めよ。とかであれば、 で求まる。 分…

最小全域木の探索について アルゴリズム ナイーブな実装だと計算量が 程度。ノード数が多いグラフでは計算量をいかに落とすかがポイントっぽい。 プリム法 グラフ の頂点全体の集合を 最小全域木(MST)に属する頂点の集合を とする。 から任意の頂点 を選び、…

グラフの探索方法のメモです。 実装の詳細というよりも、概念のメモです。 幅優先探索 1.キューに入れる(add)。訪問済にする。 2.キューが空でない限りループする 2-1.キューから取り出す(remove)。 2-2.隣接ノードに訪問する。未訪問の場合のみ、キューに入…