min_span_tree_visualizer
1.0.0
最も一般的な最小スパニングツリー（MST）アルゴリズムの2つがどのように機能するかを視覚化するC ++プロジェクト - 主にKruskalとPrim's。アプリケーションにより、ユーザーはツリー構造をランダムに生成したり、ファイルからインポートしたりして、MSTを見つけるために使用するアルゴリズムを選択できます。有用な再生機能が実装されているため、ユーザーはアルゴリズムが最終的なソリューションにどのように到達するかを段階的に見ることができます。ユーザーは、アルゴリズムを段階的に解決するか、再生速度を選択して、それが魔法のように機能するのを見る機能を備えています。
このプロジェクトは、次の2つのYouTubeビデオに触発されました。
Primのアルゴリズムアニメーション
Kruskalのアルゴリズムアニメーション
コンピューターサイエンスでは、グラフはエッジで接続されたノードのコレクションであり、いくつかの関連する重みがあります。実用的には、2つのノードの間のエッジに、メートル単位の距離、時間の時間、またはドルのコストなど、物理的な意味がある場合があります。ツリーはサイクルのないグラフです。つまり、追跡できるエッジのパスがないように構築されており、それを追跡できます。したがって、スパニングツリーは、グラフのすべての頂点を「拡張」、または接続するグラフのサブグラフです。このスパニングツリーは、合計されたときに最小重量のエッジを選択するような方法で選択される場合、「最小」スパニングツリー（MST）にもなります。 MSTは多くの最適化の問題に非常に役立つことがわかり、実際には、モラビア市の電力ネットワークを設計する際に、最初のMSTアルゴリズムが発見されました。 1
この問題を解決するために発見された最初のアルゴリズムはチェコの数学者であるオタカール・ボリブカによって発明されましたが、今日最も人気のある2つのアルゴリズムは、わずかに異なる方法で機能する貪欲なアルゴリズムの例です。
Primのアルゴリズムは、いくつかの開始ノードからのすべての発信エッジを調べ、MSTに最低の重量のエッジを追加することにより、一度に1つのエッジを構築する貪欲なアルゴリズムです。このようにして、MSTはすべてのエッジが調査されるまで連続して構築されます。
Primのアルゴリズムが一度にMSTの1つのエッジを構築するのと同じように、Kruskalのアルゴリズムもそうしますが、Nodesの間の多数のばらばらのエッジセットから始めることで、MSTであるエッジの残りのセットが1つだけあるまで、最小重量のエッジで連続的に結合することでそうします。
Chazelleのアルゴリズムは、MSTを見つけるためのほぼ線形時間アルゴリズムです。
git clone 。
リポジトリ実行のルートディレクトリから：
git clone https://github.com/Microsoft/vcpkg.git
完了したら、vcpkgフォルダーにcd使用して実行します。
./bootstrap-vcpkg.sh
最後に、実行：
./vcpkg integrate install
cd .. cd buildを実行してからcmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmakeを実行します。すべてがうまくいけば、「ビルドファイルが...」というメッセージが表示されます。これで、生成された「Minimut_Spanning_tree_visualizer」プロジェクトを開くことができます。
テストを実行するには、右クリックして「スタートアッププロジェクトとして選択」：
テストを実行するには、右クリックして「スタートアッププロジェクトとして選択」：
ojistémproblémuminimálním（特定の最小限の問題について）↩
