現在、最小全域木のトピックを学んでおり、ほとんど理解していますが、まだ理解していないことがいくつかあります。無向加重グラフを扱っています。
まず、MST を見つけるには O(E*log V) のコストがかかることを知っています。ここで、平面グラフを扱うときに、線形時間 - O(V+E) に最適化したいと考えています。
次に、単位正方形の n 個の点の例を見て、O(sqrt n) の重みを持つ MST が存在することを示すことに成功しました。問題は、この MST を見つけるアルゴリズムが見つからなかったことです。
ありがとう、または