feature image

2023年12月2日 | ブログ記事

最小全域木問題を O(|E| log log |V|) 時間で【AdC2日目】

この記事は アドベントカレンダー2023 2 日目の記事です。

きのう :

アドベントカレンダー2023始まります
この記事はアドベントカレンダー2023 1日目の記事です。 アドベントカレンダー始まります 本日(2023/12/01)からtraPのアドベントカレンダー2023です。 traP部員が日常生活、大学の講義、ハマっている趣味などを書きます。 期間は2023/12/25までです。お楽しみに! 予定カレンダーの写真 (11/29時点) 上の表はあくまで予定であり、後で変更される可能性があります ブログが投稿されるたびにTwitterにお知らせツイートが流れるので是非フォローしてください! https://twitter.com/traPtitech いかが…
アドベントカレンダー初日なのでクリスマスをネガキャンしよう!
この記事は、アドベントカレンダー2023 1日目の記事です。 はじめに こんにちは、聖夜の破壊者(クリスマス=デストロイヤー)です。ごめんなさい、YHz / イキリ虻です。 皆様はアドベントカレンダーの由来をご存じでしょうか? もとは海外の風習で、12/1からクリスマスまでの25日の間、カレンダー状になった引き出しや箱を開封していき、クリスマスまでの間1日1つ中に入ったプレゼントを受け取っていく風習です。 これにちなんで、クリスマスまでの25日の間、みんなでブログを書こう!というのがインターネットの主要プラットフォームでのアドベントカレンダーブログリレーの始まりで、traPでも…

みなさん, 論文読んでますか?
論文読んでまとめて入門記事を作って、競プロに新しい風を吹かせて欲しいんですが…

FPS や Monge のようにマトロイドやその他色々な分野についてすべてをまとめてブログにしてくれる人が必要という話になった

— tatyam (@tatyam_prime) November 26, 2023

今日は研究をしていたらおもしろいのを見つけて, しかも短いのでここにまとめておきます.

A. C. Yao, An algorithm for finding minimum spanning trees, Inform. Process. Lett., 4 (1975); pp. 21--23.

論文の本質が 1 ページくらいしかなく, とても短い!
みなさんも読んでみてはいかがでしょうか?

問題 : 最小全域木問題

連結無向グラフ と辺重み が与えられる.
辺集合の部分集合 であって が木になるもののうち, 辺重みの和 が最小のものを求めよ.

アルゴリズム

より実用的・単純になるように整理したものがこちらになります.

パラメータ を取る. (後で適当な大きさに決定する.)

前処理

頂点 に隣接する辺の集合を とする. を辺重み ざっくりソート する.
ざっくりソート とは, を要素数 以下のいくつかのグループに分け, グループ内はソートされていなくても良いが, グループの間ではソートされているようにすること.
分けたグループを とすると,

クイックソートを途中でやめるとできる. 時間, 全体で 時間.

ブルーフカ法

ブルーフカ法をやる. 以下を全頂点が連結になるまで (最大 回) 行う.

であるような頂点のリストを管理しておくことで 時間のパートがなくなり, 全体で, 時間になる.

計算量

前処理が 時間, ブルーフカ法が 時間であるから, とすれば合わせて 時間.

なんかまだ計算量を減らす余地がありそう

はい. 時間になります. その分複雑になっていて実用的ではなさそうですが…

Chazelle, Bernard. "A minimum spanning tree algorithm with inverse-Ackermann type complexity." Journal of the ACM (JACM) 47.6 (2000): 1028-1047.

実装

誰か書いて計測して ♥️
ソートって高速なので, クラスカル法との区別はかなり大変. AVX512 sort とかあるし, ソート部分にかかる時間とソート以外の部分にかかる時間が同じくらいとかなりかねない
リストのリストは遅いから, CSR 形式にして…
少なくとも は必要かな〜

あした : @H1rono_K さんが書いてくれるらしいです! :tanosimi-:

tatyam icon
この記事を書いた人
tatyam

競技プログラミングと音ゲーをしています。 AtCoder銀冠 ICPC 2020/21 Yokohama 3 位, WF 15 位 (good_yamikin) ICPC 2021/22 Yokohama 3 位 (tonosama) ICPC 2022/23 Yokohama 1 位 (tonosama)

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2023年12月11日
DIGI-CON HACKATHON 2023『Mikage』
toshi00 icon toshi00
2023年12月13日
HgameOPについて語る
noc7t icon noc7t
2023年12月25日
オレオレRustプロジェクトテンプレート
H1rono_K icon H1rono_K
2023年12月18日
GPU側でレイヤーブレンドする絵描きソフトの同期方法
tq icon tq
2023年12月16日
MacからWindowsを弄る方法?~RDP環境を作ろう~
Alt--er icon Alt--er
2023年12月4日
私的ジャンル別最強映画番付(2023年版)
botoku_izm icon botoku_izm
記事一覧 タグ一覧 Google アナリティクスについて