この質問が少し広範である場合は申し訳ありませんが、最小コストのスパニング ツリーを作成する方法を理解するのに苦労しています。これは、問題がある場合は C++ にあります。
私が理解していることから、クラスカルを使用して、スパニング ツリーを構築するための最小コスト エッジを選択します。私の考えは、エッジを最小ヒープに読み込むことです。そうすれば、最小コストでエッジを取得するためにトップから削除できます。
これまでのところ、minheap と union-find のセットしか実装できませんでした。union-find の目的と、スパニング ツリーを作成するためのソート アルゴリズムについてはまだわかりません。
アドバイスをいただければ幸いです。
編集: ユニオンの検索、minheap、kruskals、および並べ替えアルゴリズムに限定されているわけではなく、何もする必要もありません。これらは講師が提案した項目にすぎません。
これら 2 つの構造は、アルゴリズムで異なる目的を果たします。クラスカルのアルゴリズムは、サイクルを形成しない各ポイントで可能な限り安価なエッジを追加することによって機能します。特に複雑ではない数学を使用して、結果として得られるスパニング ツリーが最小であることを保証することを示すことができます。これが機能する理由の背後にある直感は次のとおりです。クラスカルのアルゴリズムが最適ではなく、安価なスパニング ツリーがあるとします。そのツリーのすべてのエッジを重みで並べ替え、並べ替えられた順序でこれらのエッジを、並べ替えられた順序でクラスカルのアルゴリズムによって選択されたエッジと比較します。クラスカルのアルゴリズムが最適ではないという矛盾を想定しているため、不一致が存在するシーケンス内の場所が存在する必要があります。この不一致でクルスカルのアルゴリズムが最適解よりもエッジが軽い場合、次に、そのエッジを追加し、それが作成するサイクルを見つけ、サイクルで最も重いエッジを削除することで、最適なソリューションをさらに改善できます。そのエッジは、追加したばかりのエッジではありません。そうしないと、クルスカルのアルゴリズムによって生成された MST にサイクルが作成され、クルスカルのアルゴリズムがサイクルを作成するエッジを追加しないためです。したがって、これは、クラスカルのアルゴリズムが最適解から逸脱したに違いないことを意味します。しかし、クラスカルのアルゴリズムがエッジをスキップする唯一の理由は、それがサイクルを作成する場合であり、これは、最適な MST にもサイクルが存在する必要があることを意味し、これも矛盾です。これは、私たちの仮定が間違っていて、クルスカルのアルゴリズムが最適でなければならないことを意味します。次に、サイクルで最も重いエッジを削除します。そのエッジは、追加したばかりのエッジではありません。そうしないと、クルスカルのアルゴリズムによって生成された MST にサイクルが作成され、クルスカルのアルゴリズムがサイクルを作成するエッジを追加しないためです。したがって、これは、クラスカルのアルゴリズムが最適解から逸脱したに違いないことを意味します。しかし、クラスカルのアルゴリズムがエッジをスキップする唯一の理由は、それがサイクルを作成する場合であり、これは、最適な MST にもサイクルが存在する必要があることを意味し、これも矛盾です。これは、私たちの仮定が間違っていて、クルスカルのアルゴリズムが最適でなければならないことを意味します。次に、サイクルで最も重いエッジを削除します。そのエッジは、追加したばかりのエッジではありません。そうしないと、クルスカルのアルゴリズムによって生成された MST にサイクルが作成され、クルスカルのアルゴリズムがサイクルを作成するエッジを追加しないためです。したがって、これは、クラスカルのアルゴリズムが最適解から逸脱したに違いないことを意味します。しかし、クラスカルのアルゴリズムがエッジをスキップする唯一の理由は、それがサイクルを作成する場合であり、これは、最適な MST にもサイクルが存在する必要があることを意味し、これも矛盾です。これは、私たちの仮定が間違っていて、クルスカルのアルゴリズムが最適でなければならないことを意味します。s アルゴリズムは、サイクルを作成するエッジを追加しません。したがって、これは、クラスカルのアルゴリズムが最適解から逸脱したに違いないことを意味します。しかし、クラスカルのアルゴリズムがエッジをスキップする唯一の理由は、それがサイクルを作成する場合であり、これは、最適な MST にもサイクルが存在する必要があることを意味し、これも矛盾です。これは、私たちの仮定が間違っていて、クルスカルのアルゴリズムが最適でなければならないことを意味します。s アルゴリズムは、サイクルを作成するエッジを追加しません。したがって、これは、クラスカルのアルゴリズムが最適解から逸脱したに違いないことを意味します。しかし、クラスカルのアルゴリズムがエッジをスキップする唯一の理由は、それがサイクルを作成する場合であり、これは、最適な MST にもサイクルが存在する必要があることを意味し、これも矛盾です。これは、私たちの仮定が間違っていて、クルスカルのアルゴリズムが最適でなければならないことを意味します。
これが、Kruskal のアルゴリズムがヒープと共用体検索構造を必要とする理由の動機となることを願っています。ソートされた順序ですべてのエッジを取得できるように、ヒープが必要です。この順序でエッジにアクセスしないと、上記の証明が崩れ、すべての賭けが無効になります。興味深いことに、実際にはヒープは必要ありません。ソートされた順序ですべてのエッジにアクセスする方法が必要なだけです。必要に応じて、すべてのエッジを巨大な配列にダンプしてから、配列を並べ替えることができます。高速ソートを使用する場合、アルゴリズムの実行時間はバイナリ ヒープの場合と変わりません。
union-find 構造は少しトリッキーです。クラスカルのアルゴリズムの各ポイントで、エッジを追加するとグラフにサイクルが作成されるかどうかを判断できる必要があります。これを行う 1 つの方法は、どのノードが既に相互に接続されているかを追跡する構造を格納することです。そうすることで、エッジを追加するときに、エンドポイントが既に接続されているかどうかを確認できます。そうである場合、エッジはサイクルを形成するため、無視する必要があります。union-find 構造は、この情報を効率的に維持する方法です。具体的には、その 2 つの操作 (union と find) は、以前は接続されていなかったノードの 2 つの異なるグループを接続する行為に対応します。これは、スパンの異なる部分に含まれる 2 つのツリーを接続するエッジを追加した場合と同様です。森林。検索ステップは、2 つのノードが既に接続されているかどうかを確認する方法を提供します。その場合は、現在のエッジをスキップする必要があります。
お役に立てれば！