Prim法とKruskal法

マヨ子@秋篠宮popstar @mayoko_

プリム法とクラスカル法って使い分けしたほうが良いんですか

みさわ @Mi_Sawa

プリムとクラスカル, 個人的に1択になる場合は, クラスカル法: 最小全域森にしたい時, 何回もある辺集合の部分集合での最小全域森求めたいような時(最初に一回だけソートしておくやつ). プリム法: "頂点uを含む連結成分の最小全域木"的な時. あたりかなぁ.

みさわ @Mi_Sawa

あと, なんも条件無い場合はクラスカル1択 (個人の感想です)

Япон Бүресе🏴‍☠️ @southerwolfie

Primはめったに使いません。

マヨ子@秋篠宮popstar @mayoko_

オーダー変わらなかった記憶

タッパーをオーブンで焼かない @DEGwer3456

クラスカル一択

みさわ @Mi_Sawa

アルゴリズム名を英語で書かなきゃいけない時は prim 1択.

semiexp @semiexp

Prim 法めったに使わないけど Prim 法を忘れていると「Invitation」をデータ構造で解くはめになる

しおしおた @shioshiota

クラスカル覚えてからプリム使ってない気がする

Япон Бүресе🏴‍☠️ @southerwolfie

Kruskalは最小全域木を求めるのに使って、Primは恋のビーンボールを轟かすのに使ってます

hogeover40 @hogeover30

プリムのほうが実装ラクじゃね （ライブラリ自作しない人並みの感想）

とーらす🌸📦🌕✨🍀 @torus711

Prim と Kruskal ，オーダーは大差ないので，基本的な問題だったら実装の容易さで Kruskal 書いてたけど，最近 Prim をライブラリ化してしまったので Prim メインになるかも．もちろん，発展的な内容だと問題の特性による

マヨ子@秋篠宮popstar @mayoko_

最初にクラスカルの効率の良いコード書いたのでクラスカルしか使ってない

マヨ子@秋篠宮popstar @mayoko_

まず森ってなんだっけってところからなんだよなぁ

semiexp @semiexp

Prim はよほどグラフが密なとき以外いつ使うんだろう

れにんぐる @omibashira

@mayoko_ あの森で待っている

とーらす🌸📦🌕✨🍀 @torus711

あ，Union-Find は元々ライブラリにしてたことに触れないとアレだった感 /prev twitter.com/torus711/statu…

マヨ子@秋篠宮popstar @mayoko_

@omibashira その森ではない

タッパーをオーブンで焼かない @DEGwer3456

プリム派の人ほとんど見たことない

タッパーをオーブンで焼かない @DEGwer3456

昔のツイートが掘り返されている

hogloid @hogloid

大昔の僕はPrim派だったけど、Kruskalに改宗してからは一度も書いてないと思うなあ

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

昔はprim使ってたけどクラスカルの万能さを知ってからはクラスカルだなぁ。グラフを隣接リストで持った方が都合が良い場合とかならprimを使うかもしれない。

そすうぽよ(すごい)(早寝早起き) @_primenumber

Primはフィボナッチヒープを使うとO(E+VlogV)なので辺の数が頂点数より十分多ければKruskalよりオーダーレベルで速い

みさわ @Mi_Sawa

ICPCみたいな, ライブラリは手打ちの状況でもクラスカル書く気がするなぁ. なんでだろう…

マヨ子@秋篠宮popstar @mayoko_

プリムとクラスカルでTLEする/しないが変わることあるのか・・・？