[graph] 最小全域木 (MST)

[ei1333]

Description

• Prim
  • フィボナッチヒープ: $O(E + V \log V)$
  • 普通のヒープ: $O((E + V) \log V)$
  • ヒープを使わない: $O(V^2)$
• Kruskal
  • $O(E \log E + E \alpha(V))$
• ブルー孵化
  • $O(E \log V)$

ブルーフカ+Primをすると $O(E \log \log V)$

File Name

src/graph/spanning-tree/minimum-spanning-tree.hpp

TODO

• [ ] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [ ] verify

note

• reference material
  • (url)
• implementation
  • (url)
• 関連 issue / PR
  • #
• verify:
  • (url)

[Luzhiled]

spanning-tree/minimum-spanning-tree.hpp

[Luzhiled]

非負重みグラフの最小全域森 - ei1333 の日記

すべて孤立点にすることでコストを0にできます 計算量は O(1) です

[ei1333]

明日は中間試験さん！？

[ei1333]

ところで single-source-shortest-pathも密なグラフについて考えていませんでしたね $O(V^2)$

[Luzhiled]

$|V|$ にするって話じゃなかったっけこれ

[ei1333]

おじいさんなのでわすれてたんだよね