Kruskalのアルゴリズム - 行列データ構造に変更しますか？

Question

このバージョンのKruskalのアルゴリズムは、隣接リストを持つエッジを表します。 代わりに隣接行列を使用するように擬似コードを変更するにはどうすればよいですか？

私はそのゼロでない限り、我々はインスタンス（i、j）のために、エッジの重みを使用する必要がありますを考えていました。 i、jに頂点を割り当てる。私はKruskalsのこの疑似コードで少し混乱するかもしれません。

Answer 1

Henryで指摘されているように、擬似コードでは、使用する具体的なデータ構造を指定していませんでした。この場合、グラフの隣接リスト表現は隣接行列表現よりも便利であるように見えます。

隣接行列については、行列のすべてのエントリをスキャンして、グラフGの行を4行目で並べ替える必要があります。隣接リスト表現を使用する場合はまったく同じことを行っています。

たとえば、PriorityQueueを使用して、エッジを降順でソートし、切断された頂点を持つエントリを破棄することができます。その後、このデータ構造を行5のfor-loopに反復することができます。