プリムのアルゴリズムを使用して最小スパニング ツリーを作成しようとしていますが、実際のヒープについて大きな疑問があります。グラフの隣接リストを頂点のベクトルになるように構成し、各頂点にはエッジのベクトルがあります。エッジには、重み、接続頂点、およびキーが含まれます。ヒープが頂点のヒープであるかエッジのヒープであるかがわかりません。頂点のヒープにすると、重みが同じ親頂点と宛先頂点からのものかどうかを判断する方法がありません。これにより、エッジの頂点リストごとにヒープを作成する必要があると思います。最後の質問は、エッジのヒープまたは頂点のヒープを作成する必要があるかどうかです。エッジのリストの場合、エッジの重みをキーとして使用する必要がありますか、それとも優先キューに実際に使用できるキーと呼ばれる別のデータ メンバーを使用する必要がありますか? ありがとう！
3 に答える
0
ヒープはペア<vertex, weight>である可能性があり、頂点が含まれます。頂点は、部分最小スパニング ツリーに既に存在する頂点から 1 つのエッジです。(編集: 場合によっては、既に部分的な MST にある頂点が含まれている可能性があります。そのような要素が飛び出すときは無視する必要があります)。
のようなエッジのヒープである可能性がありますが、これは実質的に同じです。最初のバリアントと同じですが、無視<src, dst, weight>するだけです。srcdstvertex
PS。それに関してはkey、キーは必要ないと思います。重みを比較する必要があります。
于 2013-12-14T21:16:45.703 に答える