最小スパニングツリークラスカルのアルゴリズムを使用して

Question

私は、次のような問題の最小スパニングツリーを決定するの割り当てを完了するために、クラスカルのアルゴリズムを使用しています：

私はすべてを接続する必要がある都市を、持っています。私はそれらの間に道路を建設することによって、または空港を建設することによってそれらを接続することができます。私が都市に空港を建設すると、空港を持つ他のすべての都市と結びつくようになります。

私の疑問は、次の要件である：

つ以上の最適解の場合、私は少数の空港とのいずれかを選択する必要があります。最も効率的な方法でこれをどうすれば保証できますか？

Answer 1

kruskalのアルゴリズムでは、重みの降順でエッジをソートして選択します。

ここでは、データ構造（タプルのようなもの）を使用して、エッジを<source vertex,destination vertex, weight of edge between them>として保存するとします。私たちは、重みを降順で並べ替えて選択します。

複数の最適なソリューションがある場合は、空港の数が少ない方を優先します。したがって、1つ以上のフィールド（タイプbooleanと言う）をデータ構造に追加して、宛先頂点（都市）に空港がある場合に格納します。これは<source vertex,destination vertex, weight of edge between them, has_destination_an_airport>のようになります。目的地頂点（都市）に空港がある場合はhas_destination_an_airportはtrue、それ以外の場合はfalseです。

ここで、重みの降順に並べ替えるとき、重みが同じであれば、空港を持たないもの、可能であればhas_destination_an_airportはfalseです。

を正しく実装すると、エッジをソートすると、の魔法が実行されます。

漸近的な時間と空間の複雑さに関する限り、これはKruskalのアルゴリズムと同じです。オーバーヘッドだけが、目的地の頂点に空港がある場合に覚えておく余分なフィールドのオーバーヘッドです。これは簡単なことです。