Prim法とKruskal法

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

というか、UF木をライブラリしてからはクラスカルの方が圧倒的に楽という感じ。

マヨ子@秋篠宮popstar @mayoko_

まぁそこまでレベル高い問題解いてないからかな

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

prim描いたことない。

マヨ子@秋篠宮popstar @mayoko_

木は明らかに森である。[要出典]

みさわ @Mi_Sawa

最小全域木は動的木で常勝

しおしおた @shioshiota

ダイクストラもプリムもループして、一番小さいものを探してくるのがめんどくさい。 クラスカルはコストについて考えるフェーズと使ったかどうかについて考えるフェーズが分離されてて好き。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

要はPrimちゃんが好きかラスカルが好きかという話ですよ。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

¿あれ？

ＳＫＹ/sky58🍊 @skyaozora

クラスカル法しか使ったこと無いけど、プリム法もまぁ使おうと思えば使えないことは無い･･･はず

semiexp @semiexp

Prim 法は教科書に載っているというイメージ

かつっぱ@競プロYouTuber @catupper

【今日の蟻本】 密なグラフならプリムの方が速い

酔った勢いでJOIに寄付をするおじさん @blue_jam

PrimのアルゴリズムはDijkstraを少し変えればできる

かつっぱ@競プロYouTuber @catupper

全域木のサイズは凸性があるのでなんかてきとうにやっても最小全域木になる

とーらす🌸📦🌕✨🍀 @torus711

「Prim 法は Dijkstra 法みたいなものなので」と言いながらコード書いてたら，気付いた時には Dijkstra 法が書き上がっていたのがわたしです

もる @eomole

全域木が作れるからな

かつっぱ@競プロYouTuber @catupper

離散数学力がないのに凸性が在ると適当な心持ちでつぶやいてしまった グラフの（辺集合、森の集合）がマトロイドになるので楽しいというしかなかった

酔った勢いでJOIに寄付をするおじさん @blue_jam

1．Dijkstraのコードを引っ張ってきます 2．Queueに突っ込むときのコストと距離を表すベクタに入れるコストを辺の重みそのものにします 3．Queueから取り出した辺の端点が未だに到達していないものだったら，その辺のコストを戻り値に加算します 4．これで大体Prim

酔った勢いでJOIに寄付をするおじさん @blue_jam

Prim法はグラフの構造に依存しているが，Kruskal法はマトロイドの性質さえ満たせば云々（よくわかっていない

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

Union-Findライブラリにする勢、いるんだ・・・

まーす @__math

unionfindは36行ある

酔った勢いでJOIに寄付をするおじさん @blue_jam

私はDisjoint-set data structureをライブラリにしています

酔った勢いでJOIに寄付をするおじさん @blue_jam

そういえば，Disjoint-set data structureと呼ぶ人をあまり見かけない．WikipediaとTarjanの本ではこっちで呼ばれているのに．

nise_nabe @nise_nabe

unionfind を undefined に空目

酔った勢いでJOIに寄付をするおじさん @blue_jam

僕のUF木は23行でした

有為 @uwitenpen

disjointset, クラス部分で65行あった