FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [View Raw Code]   [Original HTTPS Page]

cpplib/docs/graph/minimumSpanningTree.md at main · edge2992/cpplib · GitHub

/ cpplib Public

Breadcrumbs

  1. cpplib
  2. docs
  3. graph

minimumSpanningTree.md

Latest commit

 

History

History
21 lines (15 loc) · 549 Bytes

Breadcrumbs

  1. cpplib
  2. docs
  3. graph

minimumSpanningTree.md

File metadata and controls

21 lines (15 loc) · 549 Bytes
Raw
title Minimum Spanning Tree (Kruskal)
documentation_of graph/maximumSpanningTree.hpp

概要

  • 最小全域木を求めるアルゴリズム。
  • $ O(E \log V)$
  • 辺のソートに一番時間がかかる。
  • あとは全ての辺を一度見るだけ。

実装のヒント

  • 辺を小さい順に追加していく
  • 閉路ができなければその辺は最小全域木の辺となる。
  • 閉路の確認をUnion Find木で行う。

参考

Back | FazBrowse Home | New Git URL